This is a common issue.
In you AD there are more than one Global Catalog (GC). Each one of these servers are able to authenticate clients.
What is happening is that you unlocked the given account in one GC, but in fact, the client is authenticating against a second (or third) Global Catalog. Once the replication didn't occur yet, the rest of GC aren't aware of the account change...
In situations like this, you should reset or unlock the account in the server closest or in the same site as the client. (a client always authenticate against the closest GC available server). So, if you can, log in remotely to that server and unlock the account. This way, the unlock is immediate to the client.
If for any reason you can't login remotely or there is only one site (with two ore more GC's), you can always use any GC to unlock the account. Then, to be sure that the change is (almost) immediately available to the client, you should force AD replication to occur. (go to AD Sites and services and force replication)
Hope this helps.