Client not found in Kerberos database

[Jaap Winius]

Hi folks,

My site uses Debian squeeze for both workstations and servers with MIT  
Kerberos 1.8.3 for authentication. Although there are generally no  
complaints, from time to time users say that the workstations do not  
accept their passwords on the first attempt, even when they anticipate  
the issue and made a conscious effort to not make any mistakes. Upon  
examination of the KDC logs, I find some evidence to support their  
claims. The most obvious is this error:

CLIENT_NOT_FOUND:  jsmith at EXAMPLE.COM for krbtgt/EXAMPLE.COM at EXAMPLE.COM,
Client not found in Kerberos database

In most cases the login name is not not spelled correctly, or there is  
nothing like it in the database at all, but in others there is nothing  
wrong. Yet, this error occurs anyway.

Does anyone have an explanation for this phenomenon?

Thanks,

Jaap