Off the top of my head, I wonder whether you are passing through a proxy, so although you have specified the credentials to use when it hits the destination server, you have not provided the credentials for the proxy you are passing through.
On the SOAP adapter configuration dialog, under the ‘Proxy’ tab, there are settings for the proxy server credentials; these are separate to the credentials for the web-service itself, which are found under the ‘General’ tab.
HTH, Nick.