In order to do Kerberos, the server and client must agree on what time it is. Sub-minute accuracy is ok. Configure NTP and get sub-second accuracy, which is even better.

DNS and reverse DNS lookup of all relevant machines must be available on all of these machines. So configure your DNS, and be sure not to leave any mistakes in /etc/hosts. Naming inconsistencies may lead to odd and seemingly unrelated messages from the GSS libraries.

If these things weren't already obvious to you, you may still bump your head further down.

A few additions to /etc/resolv.conf may be useful, see xref linkend="ad_nameserving_for_kerberos"/>.