In the last part of the handshake, the workstation sends a hash of the password and a buch of other credentials (eg username) to the ESSO server. ESSO is configured to know which domain controller(s) to use and forwards the credentials to the domain controller. The domain controller checks the credentials and the hashed password against what it thinks they should be and responds to ESSO whether it thinks the credentials are OK. If the domain controller says the credentials are ok, then next ESSO looks up an LDAP server using the Windows username and resolves that back to a X500 style name (eg ORG\bill to CN=Bill Smith/OU=Sales/O=ACME) This is the name that is recorded in the ltpa token and used for the session.
From the above it sounds like the problem is with the one workstation? If so, try removing it from the domain and re-adding it, maybe this will reset its permissions within the domain.
Are you using NTLM or Kerberos as the authentication method?
What is the Windows server version and Windows client version? Is the version of Internet Explorer (I assume) the same as the other workstations?