What kind of return code are you getting from the service? We have seen instances where the remote web server is up, but the web service is not. The return code will be in the 4xx or 5xx range and will give you some hint as to what the trouble was on the far side.
