Interestingly, I woke up to this exact problem this morning. iCloud was working fine on all my iDevices for a while and then this morning my mail program was telling me my password was rejected, I was getting an error screen on icloud.com, and in settings iCloud was telling me my account wasn't verified.
I only just now figured out the problem in my case - multiple AppleIDs.
I have an appleID for Australia, USA, UK and also one for my MobileMe address (now iCloud) - that makes 4 in total. The problem I found was that the primary and secondary email addresses for those 4 accounts were overlapping.
For example, my USA account's AppleID is
email1@me.com. I used
email1@me.com as the secondary email address for my Australian account, and so on and so on in one big mess.
The way I solved it was to
delete secondary addresses for all my accounts (using appleid.apple.com) and changing primary addresses so they were unique and didn't double up with other AppleIDs.
I was actually short a few email addresses to make this happen so, because I have a gmail address, I started using
myaddress+01@gmail.com and
myaddress+02@gmail.com and it worked just fine.
For my iCloud @me.com AppleID I changed it's primary address to a gmail address as well. It worked fine. And when I verified (because it actually does send to gmail addresses) I was able to login again and it had remembered every little thing I had on it before - I lost nothing.
Maybe this is your problem as well?