Authentication given 401:Unauthorized exception

Here is my scenario. I have an ASP.Net web service deployed to my IIS on a
2003 server machine as a web site at the root of IIS. The web site has
Integrated Windows auth turned on and anonymous access off.

While running a client app (console app) from the same machine that the web
site is deployed to, I need to change the credentials to authenticate with to
a user that is different than the logged in user. So, on the proxy object to
the web service, I set UseDefaultCredentials = false and set the Credentials
to an instance of NetworkCredential passing it the domain, username and
password.

When the web service is run, I get an 401:Unauthorized exception.

I have tried instead of setting the Credentials to a NetworkCredential,
rather I create a CredentialCache object and add a NetworkCredential instance
to it with the AuthType = "Negotiate", but get the same error.

If I use the "Run As" feature to run the console app, and run it as the
other user in question, it works fine if I leave the
Credentials/UseDefaultCredentials properties alone. But if i attempt to set
those to the other user, I get the same results.

The only thing that has worked is to force NTLM authentication via the
inetpub\adminscript\adsutil.vbs script. When i force NTLM this way, it only
works if i set Credentials to a NetworkCredential. If i set it to a
CredentialCache object, i get the same 401 error.

Luckily, this is a test only issue, so we won't be shipping this way, but
wanted to see if there was something else i have missed.

Thanks,
Ryan