Time taken for authentication to work again after changing system time

Solution 1:

w32tm /resync should do the trick. This command will resync the time on the local computer to it's time source, which in an AD domain should be the authenticating DC or the PDC emulator. Running w32tm /resync /computer:COMPUTERNAME will send the resync command to the remote computer specified by COMPUTERNAME (in case you're unable to log on to the computer whose time needs resyncing).

EDIT: I just realized this might not actually fix the problem. After reading your question again, it sounds like the local clocks were already back in sync with the domain hierarchy. My apologies if this answer doesn't help.