OP, i feel your pain. I had this problem for AGES, especially with low poly models such as yours.
The problem is there simply isn't enough polys on the model for the baker to know what the hell it's looking at. You can fix it by tesselating your lo-poly model significantly. Bake that, then slap the baked texture back to your original un-tesselated model.