You get this error when you configure the /etc/krb5.conf file to use a domain name that you cannot resolve correctly. Its strange becuase often I find that if I do an nslookup of the server name, it works properly. However, if I enter the domain name of kdc server inside /etc/krb5.conf I get this error. Its a relatively easy fix. Just change the domain name into the IP address of your kdc server.

Actually, I think using an IP addresss rather than domain names to be a better way of configuring this file anyway. The reason that most people need to configure /etc/krb5.conf is to enable the ADS security model in Samba. If you find that your DNS service, required for Active Directory, to be a bit finicky or slightly unreliable and your server has a static IP then you can almost always assure that you'll get a ticket. If for some reason the DNS service on the windows box goes down, I can still contact it for kerberos tickets. Just my $.02.