Have you tried using the full username@domain as your username rather than just username ?
Have you tried changing your gmail/exchange passwords making sure you pick something strong ?
Have you been to
https://www.google.com/accounts/DisplayUnlockCaptcha on the iPhone's browser ?