Found another thread about the same issue.
Just tried following the instructions given there to "manually" add the "iCloud" account and not allow the system to automatically configure Mail by using the checkmark option in the iCloud preferences in the System Preferences app.
Follow the instrucations here:
http://www.wilmut.webspace.virginmedia.com/notes/icloudmail.html
Also refer to this Apple site for specifics as to what ports, server names to use as well.
http://support.apple.com/kb/HT4864
Just did it on my Lion Server Mac and so far not seeing the issue happen again and now seeing the proper "imap.mail.me.com and smtp.mail.me.com" server names in the Mail configuration settings and not the weird "pX-mail.me.com" versions.
Also, you can run "Connection Doctor" under "Window" menu item in Mail to verify if there is a connection issue.
Good luck.
Carlos.