You actually aren't having a problem with a firewall, but with an HTTP proxy server. This is like a firewall, but is designed to control access going out to the internet rather than coming in from the internet. To work around this, you'll need to configure the web service proxy with the URL and port of your proxy server, as well as the username and password required to get through it. That last part can be tricky depending on how your IT department has configured the proxy. Some use simple HTTP Basic authentication, some use your NTLM (Windows login) credentials, etc.
The problem is that you often don't even know it's there, because Internet Explorer is often configured by IT to auto-detect the proxy and do the right thing. When you write HTTP code yourself, you need to do it. A good starting point is below - it shows an example of doing just want you're trying to do, but in VB.NET.
But basically, you need to create an instance of System.Net.WebProxy with the URL and port. You also need to pass in an instance of the credentials (probably using System.Net.NetworkCredential) that contain your username/password.
If you can tell me what the proxy server demands (talk to your IT department), I can probably give you more specific help.
