Hey Team, it's a known issue, actively being worked on. I had a customer hit this as well. I thought it might have something to do with multi-org admins who are prompted to do a standard password reset, it takes it, but then doesn't sync, and if you re-login to different Orgs, likely existing on different back-end shards, the password sync process didn't catch up yet (or didn't take effect).
I'm not sure if that was your exact experience, but I spoke with Support today and there is an open internal case with Eng. Go ahead @Nash and open a ticket so Support can add you to the open case. Tell them to add you to the case for account password changes not syncing between some shards.