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.