.net – Error calling web service 401: Unauthorized

I get

The request failed with HTTP status 401: Unauthorized

My web service is .NET 4 running on IIS6. My client is .NET 2 running on IIS6

When I run the both client and serivce on my local host it works.
When I move the service to the web server I get the above error. I have set Allow An

I have tried every combination of anonymous access & integrated Windows authentication within IIS
I can access the web service via a brower and call it using Web Service Studio ok, it just does not work when I call from another .NET service

UPDATE

I have checked that the IUSR account has NTFS file permissions and is also added in local security policy as a USER that can access the server over network.

When I call from WebService Studio it makes two request first called gets back 401, then it calls again passing 'Authorization' and works. See below. So for some reason my anonymous access is not working. As when I only have anonymous access ticked and integrated Windows authentication unticked I cannot even access it from the brower

Content-Type: text/xml; charset=utf-8
SOAPAction: "http://tempuri.org/HelloWorld"
Host: webdev1
Content-Length: 314
Expect: 100-continue
Connection: Keep-Alive

<?xml version="1.0" encoding="utf-8"?><soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><soap:Body><HelloWorld xmlns="http://tempuri.org/"><echo>sd</echo></HelloWorld></soap:Body></soap:Envelope>

HTTP/1.1 401 Unauthorized
Content-Length: 1539
Content-Type: text/html
Server: Microsoft-IIS/6.0
WWW-Authenticate: Negotiate
WWW-Authenticate: NTLM
Date: Thu, 28 Jun 2012 12:26:33 GMT
Proxy-Support: Session-Based-Authentication

Call 2 (happens automatically)

POST http://webdev1/CSHRService/CSHR.asmx HTTP/1.1
Content-Type: text/xml; charset=utf-8
SOAPAction: "http://tempuri.org/HelloWorld"
Authorization: Negotiate YIILzQYGKwYBBQUCoIILwTCCC72gJDAiB/EG1WyqaLj3E67GA0......
Host: webdev1
Content-Length: 314
Expect: 100-continue

<?xml version="1.0" encoding="utf-8"?><soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema"><soap:Body><HelloWorld xmlns="http://tempuri.org/"><echo>sd</echo></HelloWorld></soap:Body></soap:Envelope>
HTTP/1.1 200 OK
Date: Thu, 28 Jun 2012 12:26:34 GMT
Server: Microsoft-IIS/6.0
WWW-Authenticate: Negotiate oYGgMIGdoAMKAQChCwYJKoZIgvcSAQICooGIBI..
X-AspNet-Version: 4.0.30319
Cache-Control: private, max-age=0
Content-Type: text/xml; charset=utf-8
Content-Length: 360

My code that calls the service is just

  CSHRService cshrService = new CSHRService();
  string s = cshrService.HelloWorld("d");