Newbie: "Server not found in Kerberos database"

[Michael Urban]

I am still in 'toy installation mode'.  I have set up a KDC
on a Linux machine, call it kervara.mygroup.org  I have successfully
set things up to the point that I can kinit from various clients.

I have also set up OpenSSH 3.9p1 to use GSSAPI authentication.
When I am logged into kervara, and have a valid TGT from this
realm, I can successfully ssh into kervara.mygroup.org without
a password; the keytab contains entries for the host/kervara.mygroup.org
principal.  This is the way things are supposed to work.  Life is good.

The problem comes when I attempt to do the same thing with the same
version of OpenSSH built with the same options on a Solaris machine.
In that case, the server logs a "Server not found in Kerberos database"
message and gives up.  I have looked at all the obvious candidates
(wrong DNS entry, disagreement as to host name in /etc/hosts and
DNS, etc) and come up empty.

Unfortunately, the log messages do not tell me _what_ principal it
was trying to find in krb5.keytab (I assume that this is where
the mismatch or missing entry is).

Is there a way to squeeze more diagnostic information?  Or does
this sound like a familiar problem?