Strange Kerberos Error

[T. Rectenwald]

We have three rp3410's running HP-UX 11.23 with LDAP and Kerberos configured for user authentication and authorization that are experiencing a strange Kerberos problem.

Kerberos is invoked through /etc/pam.conf as follows:

login auth sufficient libpam_krb5.so.1 try_first_pass

Whenever a user telnets, SSH's, Remsh's into the server, and is not previously trusted so that a password prompts, Kerberos fails with the following messages in the syslog.log:

login: pam_krb5: pam_sm_authenticate() begin
login: username [user1] obtained
login: [KDC reply did not match expectations] Unable to verify Kerberos V5 TGT: [server1.test.com]
login: Kerberos V5 TGT bad: KDC reply did not match expectations
login: while verifying tgt[Unknown code ____ 255]
login: [Authentication failed] Password not valid
login: pam_krb5: pam_sm_authenticate() end, retval = 9
login: pam_authenticate: error Authentication failed

The strange thing is we have the same exact LDAP/Kerberos configuration on 100's of servers and it runs fine. I don't know where to begin with errors like this, Google didn't turn up much either. Any help getting me pointed in the right direction would be appreciated.

Regards,
Tom