It would have to be Security Credentials of some sort.
The Web Service could be using Windows Authentication and the admin might have rights, the local user doesn't.
You could try to turn on Anonymous authentication on the web service and see if it works for the local user then. If it does then its a bit of a give away its Network Credentials.
Chase links around like
http://msdn.microsoft.com/en-us/library/system.net.networkcredential.aspx[
^]
Oh and for speed if you can choose one of NTLM or Basic instead of Negotiate then the credential validation takes one less web service call.