Ola Rodolfo,
Isto esta acontecendo por que o webservice que você esta tentando utilizar esta em uma rede com proxy autenticado.
o que você pode fazer para corrigir este problema é adicionar antes da chamada do serviço o seguinte código:
IWebProxy proxy = new WebProxy("proxy address", port);
proxy.Credentials = CredentialCache.DefaultNetworkCredentials;
WebRequest.DefaultWebProxy = proxy;
ou se preferir pode configurar no web.config
<system.net>
<defaultProxy>
<proxy
usesystemdefault = "false" proxyaddress="http://proxyserver" bypassonlocal="true"/>
</defaultProxy>
</system.net>
espero ter ajudado,
abraços
"Faça as coisas da forma mais simples possível. Mas não mais simples do que isto" - Albert Einstein