Try this
1. You must add <identity impersonate="true"> in Web.Config file of the web application that is calling the web service.
2. Try to use System.Net.CredentialCache.DefaultNetworkCredentials
If this does not solve your issue then follow these steps
1. Enable Anonymous access from IIS for the web service (Refer
http://support.microsoft.com/kb/324274[
^] for the details)
2. In case you dont have access to change the IIS Settings or you just dont want to allow anonymous because other applications are using it, then you can programatically provide the permissions by specifying the credential cache. This can be achieved by using System.Net.CredentialCache.DefaultNetworkCredentials.
Hope this helps.
All the best.