I tried just about everything here to no avail... iOS 5.1, exch 2003. Deleted/re-added a number of times... The mail was downloading up until a certain point, then gave the "Cannot Get Mail - The connection to the server failed" error.
Then when I changed the sync limit from "no limit" to "1 day" the newer stuff downloaded, skipping everything in between. I went up to 3 days and same thing. The fix here has nothing to do with the time limit, but more so that it was one corrupt message in her inbox that was causing the downloads to just fail and crash and burn.
I went into her inbox and deleted the first message that was not downloaded, and voila, problem solved, the error went away.
What was that message? It was an e-mail received from someone using the emoji app, which this user had also installed. These messages basically take obscure UNICODE characters and substitute an emoticon in the e-mail; if you look at the same message in Outlook it will look like this:
���⛽ ⚠ ��� ♨������������� and so forth. The app then substitutes the characters back to the icons.
Some of these messages had come through fine, this one particular did not. I don't know if it was randomly corrupt on the server or if it was just an obscure character that crashed it.
Consquently, emoji is actually built right into iOS itself and the third party app isn't even necessary. The difference is Apple's built-in version probably has a lot less options. To enable this, go to Settings -> General -> Keyboard -> International Keyboards -> Add New Keyboard... -> scroll through the alphabetical list and add "Emoji" ... On the keyboard input the user then can hit the globe icon and select the emoji icons.