iPhone 5 iCloud Account "Password Missing"

Had a strange issue tonight while setting up my new iPhone 5.  I fought with it for probably about 30 minutes before stumbling onto the solution.

After syncing with iTunes and checking "Sync Mail Accounts" to get my mail settings, I kept getting the popup error "Password Missing" for my iCloud account.  At first I wasn't sure which one it meant because I have one account that I use for iTunes & purchases, and another separate iCloud account that I use pretty much for just email.

I tried both password, neither worked. Same popup. Again and again and again. I went into mail settings and changed the description on the two accounts to make them distinctive; they were both just "iCloud" before.  The mail settings page now reflected the new descriptions. But, whenever I went back to the Mail app I was greeted with same annoying blue popup.

I went to icloud.com and logged on using the same password.  Worked the first time. I went to Apple Account Management. Logged in the first time. Verified all my info. Logged out. Tried on the phone again. Same error.

Finally in disgust, I decided to just delete the "Me" account and re-add it. When I scrolled down to the red "Delete Account" button and clicked it, I was prompted with "The Terms of Service Have Changed". ???  I agreed to the ToS... and didn't delete the account. I went back to mail. This time it prompted be for the password, but had the .Me email address. I put in the same password I'd been using all along and voila!

Very strange.