Just guessing, but I don't think it has anything to do with the phone shipping. I have two iPhone 4s , an iPad, 2 Apple TVs, and OSX Lion (all upgraded to the latest software). So, kind of the whole econsystem going, and everything is working except Mail. I converted my iTunes account (which was previously not an email address, but is now a Gmail email address) and then created the @me.com account as I described above. I get a similar error as above if I try to add the account to Mail on my Mac. Also, I get a "cannot load" error on the iCloud website if I try to launch Mail there, and any email I try to send to the new address gets bounced.
So, I'd love to hear if there is a solution, but this appears to be a significant system issue and I think all we can do is wait.