After changing my iCloud account password, which I also use to log in to macOS, I can no longer sign in to Messages which means I can't use iMessage or SMS messages on my MacBook. Every time I enter my iCloud account email and password I get an alert, "This Mac can't connect to iCloud because of a problem with [my email address]." The dialog has a link to iCloud Preferences and if I proceed to sign in there, I then get an error message that my username or password was incorrect (even though I know it's correct). This happens every time I try, the same thing happens with Facetime.
I also can no longer use the iCloud Keychain. I'm frequently (i.e. several times each hour) prompted with "accountsd wants to use the Local Items keychain." which as far as I can tell doesn't exist, so if I cancel that a few times it changes to "accountsd wants to use the iCloud keychain." Entering my iCloud password here doesn't work, I have no idea what the password could be and I don't see any way to set one in Keychain Access.
This is extremely frustrating, I've tried Apple Support but they were unable to solve it, I have an open ticket but nothing has happened for over a week. Has anyone else had a similar issue?