Ugh! It was so annoying. Here’s what fixed mine:
– Delete Gmail email account from your iPhone. Settings -> Mail -> Account -> Delete Account
– Reset your network settings. Settings -> General -> Reset -> Reset Network Settings
– Add Gmail account again . Settings -> Mail -> Add account -> Other
– Follow the instructions from Google: http://mail.google.com/support/bin/answer.py?hl=en&answer=77702