My problem was the same but I'm on Outlook .
Ok , I've fully fixed the problem on iphone4s outlook email..
I've got a hotmail.com email address so, the issue lays with the outlook server!
Follow these steps
. First go to add a new email address , do not press Outlook! Press other instead.
Add your hotmail account and password in there!
You'll still have your outlook email account added , go into your outlook and on the green slider turn email OFF! Then the new account you've added which will now be called hotmail will be the one that receives all your emails and of course you can send via this as you always have. This fixes the whole problem , no more error messages .
Hope this helps
Always go to 'other' when re adding your email account and turn off mail on your green slider on the previous email you have had problems with. Don't delete it , just turn it off. You'll leave it so it still backs up your contacts but that's all.
Mine works perfect now! I believe it's an ios7 related issue . Mine only went pear shaped two dats ago and it drove me nuts . Not anymore!
Enjoy guys
Steve