I was calling a web service from code in ASP.net and got the dreaded 401 error. The web service was fine from a browser (but I couldn't execute anything since the test page only works on the local server and this remote). I used the Visual Studio "Add Web Reference" and logged into the HTTPS web service, it all seemed fine.
In the end, I ran up Fiddler (the web browser tool) and accessed the web service in the browser, the header came back telling me that the web service was expecting "Negotiate/NTLM" authentication and I was attempting to authenticate using basic. It now works and here is the code I had to use:

MyWebService service = new MyWebService();
CredentialCache myCredentials = new CredentialCache();
myCredentials.Add(new Uri(service.Url), "Negotiate", new NetworkCredential("MyUserName", "MyPassword"));
service.Credentials = myCredentials;
service.PreAuthenticate = true;
// Call functions etc

Note, I did not require any special certificate code which some people have suggested and this works on an HTTPS connection. I also did not need to specify the domain in the Add() function, just the username and password.