We have solved the issue long time ago, so I don't remember the issue accurately. But as I remember, it was related to replication. There were multiple domain controllers serving the domain. If first CommitChanges saves data to dc1, the second may go to dc2. The solution is to add users in batch and replicate the domain controllers then update the password in another cycle.
Hesham A. Amin My blog twitter: @HeshamAmin