Odd problem with Active Directory

[Jeffrey Watts]

Hello, I've been working with Kerberos for the last few months getting Linux
and HP-UX servers to authenticate against AD.  I've been using pam_krb5 and
nss_ldap on Linux, and pam_krb5 and LDAP-UX on HP-UX.

Anyhow, I'm having an odd issue with a few Linux servers.  Our domain
crosses many networks, so using DNS to find domain controllers hasn't worked
very well, so I'm using three separate kdc entries in /etc/krb5.conf.  I
have dns_lookup_realm and dns_lookup_kdc set to false.

I'm using Kerberos to secure the LDAP connection.  Here are the relevant
lines from my ldap.conf:
use_sasl on
krb5_ccname FILE:/etc/.ldapcache
sasl_secprops maxssf=0

When I initially migrated the systems I used 'net ads join' to create a
machine account, and then I run 'kinit -k MACHINENAME$ -c /etc/.ldapcache'
in a cronjob to keep a fresh ticket.

I have all systems pointing to those three KDCs, in the same order:
kdc1
kdc2
kdc3

They were all running Windows2003 (not R2, but using the Windows2008R2
schema).  Two weeks ago, kdc1 was upgraded to Windows2008R2.  Suddenly five
of my Linux boxes (out of 109) stopped being able to check out tickets from
that particular Windows2008R2 server.  This includes RHEL4 and 5 systems.
They are located in different networks, and identically configured systems
do work (for example, devserver1 will work, but devserver2 will not).  The
keytab still works with the Windows2003 servers.  The remaining 104 systems
work fine with no issues.

I've deleted the machine accounts and the local keytabs and recreated them,
but those same machines still have the same problem (can authenticate
against Win2003 servers but not Win2008R2).  The last successful ticket
checkout for all five of them occurred within an hour of each other, and it
appears to be during the time when that KDC was upgraded.

There is another Windows2008R2 server (kdc4) on our network that we don't
normally use, and if I point those systems to it they have the same problem,
so it seems to be some issue involving Windows2008R2 and these particular
systems.

Here is the error that 'kinit -k MACHINENAME$ -c /etc/.ldapcache' gives when
pointing to to the Win2008R2 server:
kinit(v5): Key table entry not found while getting initial credentials

Here are my Kerberos versions:
RHEL4:  krb5-workstation-1.3.4-62.el4
RHEL5:  krb5-workstation-1.6.1-36.el5

On the 64-bit systems, both the 32-bit and 64-bit libraries (krb5-libs) are
installed.  I know I must be missing something, as my understanding of
Kerberos is purely functional and isn't comprehensive.  Any advice would be
appreciated.

Thanks,
Jeffrey.

P.S.  If anyone can recommend a good (and preferably succinct) book on
Kerberos written for a sysadmin's use I'd appreciate it.  As I said I have a
functional understanding and I'd like to know more about concepts and
strategies for implementation.  I'm not interested in a book more oriented
towards programmers.