It took me a while to figure it out, so I thought I post it, so people in the future might be able to avoid the waste of time. I had a machine which is not joined in our domain that just couldn't log on to the OCS system. The client was a Windows XP machine and the authentication on the front-end OCS server was correctly set to "NTLM + Kerberos".
After a lot of googling and trying different things, I found a post mentioning that the minimum key requirements on NTLM on Windows 2008R2 are 128-bits and this key length is not supported in Windows XP (only on Windows 7).
With this link: http://technet.microsoft.com/en-us/library/dd566199%28WS.10%29.aspx I was able to remove the 128-bit requirement and things were all dandy again.