This is an issue that occured during a training event. I didn't solve this even though a similar issue has occured before. Credit has to go to my very smart course delegate. He shall remain nameless.

The issue

If you should get a 401 error when accessing a web service but when everything else seems fine the following can help:

WebService CRMService = new WebService()
CRMService.Credentials = System.Net.CredentialCache.DefaultCredentials;
logonresult CRMLogon = CRMService.logon(this.txtUserName.Text.ToString().Trim(), this.txtUserPassword.Text.ToString());
CRMService.SessionHeaderValue = new SessionHeader();
CRMService.SessionHeaderValue.sessionId = CRMLogon.sessionid;

There is a Microsoft Support article that discusses this point:
http://support.microsoft.com/kb/811318

The previous article that is related to this is a 'Web Services Logon Tip'.