Why am I having trouble entering a new Gmail password in Mail (and Internet Accounts)?
I had this issue recently. There are some answers here, but what worked for me was I had to sign out of my iCloud account first. Add/Update the Google password (should now work) then sign back into iCloud.