As an addition to Jacobs comments Kerberos is also very sensitive to DNS issues - make sure that you have both regular and reverse DNS entries for both servers. Kerberos will do a reverse DNS lookup on the caller and tell the caller to piss off if a reverse DNS lookup fails, etc.