Customers domain controllers where both virtual and due to CPU congestion it seems that time had been drifting.
So it was 5 minutes behind, and so was the clients. The fix is as follows.
1. Find the DC that have the PDC role.
netdom query fsmo
2. Issue the follwing command to sync the time with some of the pool.ntp.org servers.
w32tm /config /syncfromflags:manual /manualpeerlist:"0.pool.ntp.org 1.pool.ntp.org 2.pool.ntp.org 3.pool.ntp.org /reliable:yes /update "
3. After the time on the PDC again is correct, then issue following on the other domain controllers, that are not PDC.
w32tm /config /syncfromflags:domhier /update
4. let the clients resync there time, either wait for it to happen or issue the following