On each host type hostname --fqdn and make sure that matches what Kerberos thinks the hostname is. I bet this is your problem. Also, drop the enctype related parameters from /etc/krb5.conf although not /etc/krb5kdc/kdc.conf. This isn't actually a problem, but the enctype stuff is not needed by your configuration and may break things in the future.