are you using some kind of authentication? are you using a proxy and that proxy needs authentication information? see
http://support.microsoft.com/default.aspx?scid=kb;en-us;811318or if you are using GET/POST, you need to modify machine.config:
<webServices>
    <protocols>
      <add name="HttpSoap"/> 
         <add name="HttpPost"/>
         <add name="HttpGet"/>
      <add name="Documentation"/> 
    </protocols>
</webServices>see
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetsec/html/SecNetch10.asp