I have read on a few posts (stack exchange, reddit and others) that sometimes it does take multiple password changes, and attempts to login, change password again, attempt again, rinse and repeat. There’s no indication what’s wrong with the password or the process, but eventually it may work and you can then revert back to your original credentials. However, I think that is more an issue with their load balancing and that not all servers are configured the same.
I also found several articles stating MS was deprecating TLS1 and 1.1 from 2018 and 2020.