I just experienced a similar problem. I could not connect to my iCloud email account even though I hadn't changed the password and should have been stored correctly in my Keychain. I clicked on the iForgot link and attempted to reset my password from the apple id site. I successfully changed the password but was still unable to log on to iCloud mail on my iPhone or laptop.
After several minutes of extreme frustration (do you know that you still have to pay for customer care if you don't have a current apple protection plan for a device even if it's network not device related???) I realized that I was able to log on with my new password to all the apple sites (store, support etc) but not iTunes or iCloud. This baffled me for a few minutes and I thought to check my Keychain passwords as mentioned earlier in this post. Didn't help much though because mine were also listed as a bunch of random characters.
I went back to the apple ID site to change my password again thinking that maybe it just didn't update all the way through the system. At this point I realized that if you just type in your apple ID (fake example: kittyfan42) it automatically fills in the @me.com. This is true for all the apple sites. Since I've had a mac email address since they came out (sometime before 2004) my iCloud and iTunes accounts are set to @mac.com. This is confusing because if you send me an email to kittyfan42@mac.com and a different one to kittyfan42@me.com they go to the same place. HOWEVER, it turnes out that if you change the password to kittyfan42@me.com it DOES NOT automatically change the password to kittyfan42@mac.com.
I went back to the apple ID reset site and entered kittyfan42@mac.com (typing out the whole thing) clicked the option to reset with the questions and got a whole new set of prompts (it was a struggle trying to remember my answers from 10 years ago!). Reset that password successfully and was able to log on to my iCloud account.
Hope this helps.