I had the same issue as both of you. I created my iCloud ID from my Apple ID which was a now defunct @mac.com email address. After I had the account set up I created an @me.com email address. Whenever I tried to send anything from my new iCloud email address it would fail because it would try and send it out over the @mac address. It would receive at the @me address fine, just couldn't send any email from it.
This is how I solved it:
1. I went to
http://appleid.apple.com and logged in. My primary email on the account was and still is an @gmail account. But underneath that there were alternate email addresses. In my case it listed the @mac address. I deleted it from the alternate email list and in its place showed up my @me address. Finally it seemed like I was getting somewhere. I saved my changes and logged out.
2. To get the change to carry over on my iPhone and iPad I had to go to Settings > iCloud and select delete account. If you want to avoid duplicates (when you re-add this account) you may want to choose that your device deletes what has been synced to it from iCloud.
3. Finally, re-add the iCloud account, but for me there was one catch. My Apple ID that the account was created with was an @mac address. I had to login to the account with the new @me address instead. After it was logged in it acted just like I logged in with the @mac address only my new @me address actually let me send email!
Hope this helps you guys out.
