I saw the same problem after a password change.
Updating the accounts with the new password was not enough, i had to remove and add again before they began to work.