We had a problem recently with our software not working on a Windows XP Professional (32-bit) machine that was in a domain with a domain functional level of 2008 R2. Our client software was producing an error about not being able to create the necessary objects when it was trying to talk to our server side software running on their DC. After several days of pulling hair it boiled down to there being a bug in Windows XP's kerberos.dll where it does not speak AES to the DC.
To see if you are getting the problem download and install wireshark on the workstation or the server and capture packets between the machines when you are getting the problem. look thru the capture to see if there is a "KRB5 - TGS-REQ" packet sent from WinXP to the server, with a "KRB Error: KRB5KDC_ERR_S_PRINCIPAL_UNKNOWN" response. Drill down into the "KRB5 - TGS-REQ" packet, TGS-REQ->KDC_REQ_BODY->Encrytion types if there is no AES encryption type then you probably have the same problem I did.
AES encryption for Kerberos comes into effect when the domain functional level is Windows 2008 or higher.
We solved the problem by applying the following hotfix (requires SP3) http://support.microsoft.com/kb/969442