The authentication mechanism is unknown

Question

I'm attempting to authorize access to a third party program by checking their credentials against Active Directory using NTLM.

This solution has been working for a long time - as it a rolled out product for 5+ years. I have it working on our main domain (of which I am not an administrator) and on a Virtual Machine which is a domain controller running on Server 2008.

I am only having issues on my Server 2003 virtual machine (domain controller) where instead of logging on it responds with this "The authentication mechanism is unknown" error message.

I have no problem authenticating with NTLM from the local machine when I use my test tool which utilizes the same code, the issue seems to be only from outside the PC.

I am using the same machine to connect to all these servers, which is not on any domain (and should not be) as it's a scanner.

I am certain that this has to be a configuration issue with my Server 2003 machine but I have been unable to find out what the cause is. My searching online has revealed very little related information and nothing useful as of yet.

I have tested it with the Windows Firewall turned off and with the Windows Firewall service disabled.

Edit: Just ensured that NTLM was enabled in the domain security settings (although I've never had to do this before) by giving Lan Manager Authentication to allow to send LM & NTLM responses as described at this webpage. Unfortunately the issue still persists.