I just switched Iphones, use Gmail with two step verification and Exchange to connect my computer and my phone. I COULDN'T GET MY EXCHANGE TO WORK on my new phone and searched all over the web. Lots of others have this problem. I want to post that I found the answer.
http://support.google.com/a/bin/answer.py?hl=en&answer=2716936
Google discontinued Exchange as of 1/1/13. They have a new system now.** It was grandfathered on my old phone, but if you switch, or run a re-install, it will wipe out the Exchange you had set up. The new system is described really well in:
http://www.redmondpie.com/set-up-carddav-on-iphone-to-sync-google-gmail-contacts-without-exchange/
Make sure you use your google email address, not your "user name" under "user name". Once I moved to cardDAV and calDAV, it worked just fine.
* If you use Two Step Verification, just put in the application specific code instead of your regular Google password. **