Many people had this same issue. I solved it by deleting all files from the following folder:
/Users/<YOUR HOME FOLDER>/Library/Application Support/iCloud/Accounts
I was then able to get into the iCloud preference pane, where it asked me for my new password. After giving it, all was working again.
Don't even have an iCloud folder on my whole computer.