Check what the result of the following command is on your machines: hostname -f
I have two machine. One shows the actual FQDN for the machine, and I can log into it with Kerberos tickets fine. The other has localhost.localdomain set as the FQDN, and login doesn't work. I discovered this by setting the sshd log level to DEBUG3 and looking through the logs, until I spotted a line noting that no principal matching the host was found in the keytab, despite the principal being present.
