Got the above error message on a users iPhone today – It was easy for me to trouble shoot as the user also uses an iPad and indicated he was also having problems downloading mail on that device.
Symptoms: When the iPhone mail app is accessed a notification appears towards the bottom for a number of seconds indicating “Downloading” but no new e-mails are downloaded and after a few more seconds the “Server error – Contact your server administrator – Cannot get mail” error message appears.
If you’ve already tried adding/removing the ActiveSync account details (and all the other recommended troubleshooting steps) and your device still cannot download e-mail – go back to the day your iPhone/iPad stopped receiving mail in Outlook (or whatever desktop client you normally use) and delete all mails from that day. Also empty your “Deleted Items” to be safe.
Your device cannot download new e-mails because one of the e-mails you’ve received has become corrupted and is now holding up other mails in the queue.
Once you’ve deleted the corrupted mail you should then be able to download the newer ones.