Just curious, what happens if you change their password from 365 Admin Portal?:
It says the password was changed successfully (and I get a successful user password change notice in my Admin mail box as well),
However, The password does not work
PCSAD2 This is the name of the Domain controller Server AD Sync is installed on.