/tmpdirectory on his workstation. It contained several files that looked like this:
Where "10993" was the user's old UID.
The solution to the problem was to delete all these files. So, on the user's workstation we did:
# cd /tmp # rm -rf krb*
After that, the user could log in with his new UID.