If you were using Apple Mail with a MobileMe account, it will get upgraded to Apple’s iCloud service when you opt into iCloud. After this conversion, you may run into a random error sending/receiving email stating “The iCloud IMAP server p99-imap-mail.me rejected the password”.

When this happens, you can either wait it out, or try quitting and relaunching Mail. Some users experiencing this issue have reported that changing their iCloud password fixed things, and others have reported that manually creating an account in Apple Mail (instead of using the mail account configured by the iCloud system preference pane) and pointing it to imap.mail.me.com did the trick.