Your problem can be two things.
A: Your bitrate is way too low. try using about 110kbps.
B: Check your quantisizing values. Make sure that your maximum quantisizer is not above 25 or so. The higher the quantisizer, the worse the video quality will be (it also affects file size).
I hope this helps some.