In ase it helps someone...
I've been having a similar problem for the last week but without the specific p04 part:
Connections to the server “imap.mail.me.com” on the default ports timed out.
I'm not sure it is the same issue you guys were having but the main problem here was that the outgoing iCloud server kept showing as Offline in the list. After a bit of research, I went into the Mail preferences , opened the Edit Outgoing server list and noticed that the outgoing server was set to imap.mail.me.com. So I reset it to smtp and used all the settings from here:
http://support.apple.com/kb/HT4864?viewlocale=en_US&locale=en_US
and now everything seem to be working again. Hopefull this might help someone else.
Bo