I was getting this error in the server logs when trying to ssh into a kerberos enabled box and although my ssh client was getting a principal for the machine host/machine.ox.ac.uk@OX.AC.UK I wasn't getting logged in. Now looking on the net it seemed that it was likely that I didn't have the matching principal in the keytab file. But a klist -k /etc/krb5.keytab showed all the correct keys. The next thing I checked was that the DNS records matched host machine.ox.ac.uk and host 192.0.2.0. After running round in circles I checked /etc/hosts to find the line 192.0.2.0 machine and because my machine used the hosts file before DNS it was looking for the principal host/machine@OX.AC.UK which of course didn't exist.
This whole saga would have been much easier to debug if the error message had just included the principal that wasn't present in the keytab file. The machine was a server Ubuntu 6.10 install. Strangely it seems that my desktop Ubuntu machine has the machine name only associated with 127.0.0.1 and not the external IP, although this machine uses DHCP to get its IP.