LinuxQuestions.org - NFS / Kerberos issue

I have a couple of machines running Fedora Core 5 that automounts home folders from an NFSv4 server running CentOS 5.
The client machines are running in Xen and are clones (with newly generated NIC's and separate IP addresses and so on).
The clients authenticate to the NFS-server via kerberos, and the users who log in also use kerberos.

One of these clients has now failed twice in as many days. It's simply impossible to log in to the machine, ssh simply freezes after delegating credentials. When the autofs service is shut down, it is possible to log on again. Root can always log on, most likely because no home folder is mounted for root.
Root can, however, not manually mount a folder from the NFS-server after this has happened. The other clients that have not had this problem can still mount the home folder fine.

The only thing I can find in any log is the following that pops up on the NFS-server:
Jan 16 13:34:24 nfsserver kernel: NFSD: setclientid: string in use by client(clientid 478d5716/000002bb)

These messages show up a couple of times around the time that this behaviour happens, and I have never seen errors like it in the logs before.

Does anyone have any idea what could be happening here, or where I should even start looking for an answer? Google doesn't give me very much help with only that log to go on.