Someone else might have an easy answer, yet what leaps out at me, when I read this, is that we have no code. Nor do we have a way to ensure you are, indeed, sending the correct auth data to the Web Server. As you might imagine, this makes it difficult to help you debug.

Can you write and run a simple "test case", just enough code to test out the NTLM auth bits? If that breaks, feel free to edit your post with the code, removing the actual login and password info, of course.

How's that sound?