Este é um problema de mapeamento de território. Seus hosts provavelmente estão sendo mapeados para nenhum reino.
Use /etc/krb5.conf
[domain_realm]
.example.com = AD.EXAMPLE.COM
ou, de preferência, o equivalente DNS
_kerberos.example.com IN TXT AD.EXAMPLE.COM