I've traced an issue that's been plaguing us down to a "simple" problem:
Kerberos tickets are not syncing with OS X Open Directory password changes.
Another way to put this:
Expired/expiring ticket renewal requests are being signed with old keys until the machine is rebooted.
How can I get these back in sync?
