Authentication Error when accessing Sharepoint list via web service

Question

I wrote a windows service a few months ago that would ping a Sharepoint list using _vti_bin/lists.asmx function GetListItemChanges. It was working fine until a few weeks ago when my company upgraded our Sharepoint instance to SP1.
Now whenever my service attempts to access Sharepoint I receive an 401.1 authentication error:

Error:

You are not authorized to view this page
You do not have permission to view this directory or page using the credentials that you supplied.
Please try the following: Contact the Web site administrator if you believe you should be able to view this directory or page.
HTTP Error 401.1 - Unauthorized: Access is denied due to invalid credentials.
Internet Information Services (IIS)

I have checked and my privileges on the site have not changed. here is the code In which I call the list:

Lists listsService = new Lists();
listsService.Credentials = new NetworkCredential("UserName", "Password", "domain");
Result = listsService.GetListItemChanges("List name", null, dTime.ToString(), null);

It has also been brought to my attention that basic authentication may have been disabled on our farm. I don't believe I'm using that but I may be mistaken.

Solution

Based upon the information provided, I doubt this is a programming error. Can you get access to the IIS Manager interface on the server hosting the SharePoint site? If so, check the valid authentication technologies permitted. Are anonymous connections allowed? Is Windows Integrated Authentication enabled? HTTP Basic auth? Ask your infrastructure/SharePoint people about the possibility of a double-hop (proxy). If so, that might work too, but it's a pain to setup (Kerberos delegation). The NetworkCredentials class appears to support all of the standard authentication schemes supported by IIS (except for forms):

http://msdn.microsoft.com/en-us/library/system.net.networkcredential(VS.80).aspx

You might need to have the infrastructure people set SPNs for the SharePoint web front end:

http://support.microsoft.com/kb/929650

I advise against changing anything via IIS Manager, however. Have your SharePoint Admin make the changes to the authentication techs permitted for the site via SharePoint Central Administration.

Regards, Sam