1) I had to do the following with my configuration: (Add BackConnectionHostNames or Disable Loopback Check) http://support.microsoft.com/kb/896861
2) I was working off a dev system on an isolated dev network. I had gotten it working using the dev system's computer name in the URL to the web service, but when I modified the URL to the URL that would be used in production (rather than the computer name), I started getting the NTLM error.
3) I noticed the security log showed that the service account failing to login with an error similar to the one in the MSDN article.
4) Adding the BackConnectionHostNames made it so I could log into the server via a browser running on the server, but the service account still had NTLM errors when trying to authenticate for the web services. I wound up disabling the loop back check and that fixed it for me.