For months, I've been getting the Lion Mail prompt asking me for my iCloud password, even though its on the keychain, hasn't changed, and no other servers have issues. I'd click Cancel and some days the account would work, others it would just keep asking me over and over and stay offline all day. I just ignored it, thinking Apple would fix things.
This past week, I've found a solution that works 100% of the time for me. When I wake my computer in the morning and it won't connect to iCloud mail, I log into my iCloud account in Safari and open mail there, then log out. Instantly, Mac Mail works again. One time last week, iCloud web mail itself would not open and gave me a web crash message and a 'report to Apple?' dialog.
One time a month ago, iCloud-web told me that my account was suspended and I had to go to iforgot.apple.com to reset my password - even though I'd never had any invalid login attempts. The Mac and iPhone gave me no hint that that was a problem - only found out by going to iCloud in Safari. Either somebody tried to hack my account - and that suspended it - or the iCloud servers lost track of my proper password and all of my devices trying log on looked like invalid password attempts. Who knows. Entire iCloud infrastructure is way below Apple's standards for quality IMHO.
So... I think the issues are on Apple's end in their iCloud server / load balancing architecture. I'm just surprised that this has been going on for so long and that some of the world's brightest engineers (Apple) have not managed to fix it yet.
Cheers,
Karl