I had the exact same problem. I found the answer at the following URL. I have excepted the piece that helped get me on the right path.
4.1.18 Remote Connections to a SOAP/HTTP Endpoint May Fail Using Integrated Authentication
Remote connections to a SOAP/HTTP endpoint may fail when the SQL Server service account is a domain account and authentication for the endpoint is set to INTEGRATED, even though local connections succeed. The problem can occur when the Service Principal Name (SPN) is registered to the local system account. You can work around the issue by either registering an SPN for the SQL Server Service account or specifying NTLM authentication for the endpoint. For more information about registering an SPN, see "Registering Kerberos Service Principal Names by Using Http.sys" in SQL Server Books Online.
Then in SQL Books I found the following;
To support mutual authentication under Kerberos, an instance of SQL Server 2005 must associate a Service Principal Name (SPN) with the account it will be running on, such as a local system account or domain user account. The specific details for SPN registration by a specific instance of SQL Server 2005 are determined by the type of service account it has been configured under. If SQL Server 2005 is running under the local system account or network service account, SPNs must be registered under the computer name. If SQL Server 2005 is running under a domain user account, SPNs must be registered under the domain user name.
To enable association of an SPN to the account that the instance of SQL Server 2005 is running on, use the Windows SetSPN.exe support tool. The tool adds the SPN for the computer name on which the instance of SQL Server 2005 is running under the Windows domain service user account located in Active Directory. In this scenario, the SetSPN.exe tool can be used to add two SPNs: one for the NetBIOS name and another for the fully qualified DNS name.
For example, if the SetSPN.exe tool is executed from instance of SQL Server 2005 running on
MyComputer, the following two SPNs are associated with the account the instance of SQL Server is running under and must be added to directory:
setspn –A http/MySQLHost MyDomain\MySQLAccount setspn –A http/MySqlHost.Mydomain.Mycorp.com MyDomain\MySQLAccount