Kerberos is based on encrypted timestamps. If theres more than a 5-minute difference between the KDC, client, and service computers, authentication may fail. Synchronize all the clocks for all computers using the NTP service (or another network time server).