Very odd Kerberos behavior.

[KernelPanic]

The gist of our krb5.conf file that has been working so well:

[appdefaults]
ticket_lifetime = 24000
forwardable     = true
forward         = true

[libdefaults]
default_realm    = DOMAIN.MYCOMPANY.NET 
dns_lookup_realm = false
dns_lookup_kdc   = false
max_retries      = 1

[realms]
DOMAIN.MYCOMPANY.NET = {
        kdc = tcp/kdc01.mycompany.net
        kdc = tcp/kdc02.mycompany.net
        kdc = tcp/kdc03.mycompany.net
        admin_server = kdc01.mycompany.net
        default_domain = DOMAIN.MYCOMPANY.NET
}

A couple of weeks ago our ssh client stopped authenticating using Kerberos/gssapi-with-mic. We were getting this error:

Cannot resolve network address for KDC in requested realm

Some sniffing of the traffic reveals that our server is sending out DNS queries for "tcp/kdc01.mycompany.net" which of course, fails. I can't remove the tcp/ flagging because its required for kinit to get a ticket. UDP is too small. This behavior seems absolutely wrong to me. Has anyone seen anything like this?

Added:
I tried changing the kdc entries to be IP addresses and the DNS packets showed queries for "tcp/1.2.3.4.mycompany.net" being sent instead.