I really doubt it is connected with password change itself.
- What kind of changes was done before this start to happen ?
- How many PCs this affects ?
- Is your Active Directory Env healthy ? (replication/DNS/DFRS etc)
- Is there anything specific in the workstation logs ?
Thanks,
/d