Since they have 2 different machines that are connecting to your AD domain, when they change their domain account's password on one machine, the other machine must still be connected using the now old password. And as their old machine attempts connections, they are failing (again, due to the old password). The machines could have a Service configured to use the user account to run, instead of the Local System account. Or, there could be Scheduled Job(s) set to run, using the user account for authentication. Either way, they are connecting from the other machine with the now "old" password.
Your AD domain must be running account policies that limit the number of failed login attempts before the accounts get locked out.
Check the Group Policies (Active Directory Users & Computers -> right click on your domain -> Properties -> Group Policy tab -> Edit whatever policy is in there -> Computer Configuration -> Windows Settings -> Security Settings -> Account Policies -> Account Lockout Policy ->Account Lockout Threshold!!!)
See what value is in there. The default is 0 (to disable the setting) but I bet you have a higher value in there, like 3 or so.
What you can do is change this setting to 0 to turn off this setting. Then, republish the GP, and that should take care of it.
Now, you have to decide IF you even want to do that! It is good, from a security, to enable the Account Lockout Threshold. If disabled, a dictionary attack from a remote evil person could be done until access is granted! And you don't want that.
