No principal in keytab matches desired name

[petesea@bigfoot.com]

I have 4 - Mac 10.4 (tiger) systems that stopped accepting gssapi-keyex 
authentication via ssh.  Running sshd in debug mode shows:

   No principal in keytab matches desired name

/etc/krb5.keytab is correct and contains only one principal (2 encryption 
types) which corresponds to the canonical name of the host.  DNS shows 
both forward and reverse lookups are correct and match what's in the 
keytab.

The KVNO listed in the keytab matches the KVNO for the service principal 
returned by running "kvno <service>".

/etc/hosts does not have any name matching this host... in fact it only 
contains the basic localhost/broadcast host entries.

/etc/krb5.conf is correct and exactly the same as the /etc/krb5.conf on 
several other macs (10.3 and 10.5).  I even tried starting sshd with 
KRB5_CONFIG set to a specific krb5.conf containing a default_keytab_name 
entry... just to make sure the keytab was actually getting used.

I can't find any relevant messages in /var/log/system.log or 
/var/log/secure.log.

I've tried ssh'ing from multiple client hosts (include the same host as 
the server) but all fail with the same error.

I'm pretty sure the 10.4 systems stopped working right after a Software 
Update (to 10.4.11).  Unfortunately, I didn't perform the update, so I'm 
not sure what level they were at before or exactly what was updated.

Any idea what's going on and/or anywhere else to look for the problem?