I've been working with a MobileMe/iCloud tech on this issue for the last two days. I'll report when it's finally solved.
For the last 18 hours, all MobileMe email will not push to either my Mac or iPhone. On both, get similar warning/error message regarding incoming server not responding. VERY frustrating.
Is there definitely a server issue at Apple's end?
As of today, I changed some settings, and so far it's working.
I'd rather see that Apple fixes its LDAP-servers. LDAP isn't rocket magic, OpenLDAP is robust enough, and failover/loadbalancing isn't that hard once you know what you are doing.
I do assume that the 'eat your own dogfood'-philosophy applies at Apple, and thus that they are running postfix/dovecot/LDAP on OS X.
So, the support guy thought he got it fixed with a few password changes and such, but alas, that ended up not working for good.
As of today, I changed some settings, and so far it's working. This applies to both iOS and OS X.
First, turn off Mail and Notes in iCloud preferences.
Then, in Mail, add an account using your full @me.com address as username, your password, and the IMAP server "imap.mail.me.com". The SMTP server is "smtp.mail.me.com", and uses authentication.
In Mail.app, hold "Option" when you click "Continue" after entering your email address and password to prevent Mail from automatically adding an iCloud account.
Now, you're essentially using iCloud email separate from the rest of iCloud, and so far with this setup, I have not had any issues.
For more information on the server settings, see http://support.apple.com/kb/HT4864.