I have spent several hours trying to resolve this problem, so I wanted to share my findings in case someone else might have the same problem.

I had a web part which was calling out to a WCF service on another server to get some data. The code I had was essentially

using System.ServiceModel;

using System.ServiceModel.Channels;

...

var binding = new CustomBinding( new HttpTransportBindingElement { AuthenticationScheme = System.Net.AuthenticationSchemes.Negotiate } );

var endpoint = new EndpointAddress(new Uri("http://someotherserver/someotherservice.svc"));

var someOtherService = new SomeOtherServiceClient(binding, endpoint);

string result = someOtherService.SomeServiceMethod(); 

This code would run fine on my local instance of SharePoint 2010 (Windows 7 64-bit). However, when I would deploy it to the testing environment, I would get a yellow screen of death  with the following message:

The HTTP request is unauthorized with client authentication scheme 'Negotiate'. The authentication header received from the server was 'Negotiate,NTLM'.

I then went through the usual checklist of Windows Authentication problems:

• Check WCF bindings to make sure authentication is set correctly
• Check IIS to make sure Windows Authentication is enabled and anonymous authentication was disabled.
• Check to make sure the SharePoint server trusted the server hosting the WCF service
• Verify that the account that the IIS application pool is running under has access to the other server

I then spend lot of time digging into really obscure IIS, machine.config, and trust settings (as well of lots of time on Google and StackOverflow). Eventually I stumbled upon a blog post by Todd Bleeker describing how to run code under the application pool identity.

Wait, what? The code is not already running under application pool identity?

Another quick Google search led me to an MSDN page that imply that SharePoint indeed does not run under the app pool credentials by default. Instead SPSecurity.RunWithElevatedPrivileges is needed to run code under the app pool identity. Therefore, changing my code to the following worked seamlessly

using System.ServiceModel;

using System.ServiceModel.Channels;

using Microsoft.SharePoint;

...

var binding = new CustomBinding( new HttpTransportBindingElement { AuthenticationScheme = System.Net.AuthenticationSchemes.Negotiate } );

var endpoint = new EndpointAddress(new Uri("http://someotherserver/someotherservice.svc"));

var someOtherService = new SomeOtherServiceClient(binding, endpoint);

string result;

SPSecurity.RunWithElevatedPrivileges(()=> 

{

    result = someOtherService.SomeServiceMethod(); 

});