Just encountered this while attempting to call an 'https' web service that required NTLM authentication.
"The HTTP request is unauthorized with client authentication scheme 'Anonymous'. The authentication header received from the server was 'Negotiate,NTLM'."
Changed clientCredentialType to 'windows'. Do this in the app.config.
<transport clientCredentialType="None" proxyCredentialType="None"
<message clientCredentialType="UserName" algorithmSuite="Default" />
<transport clientCredentialType="Windows" />
Do not change security mode to 'TransportCredentialOnly' the service is 'https'. That threw me, I saw that solution on several sites but they were addressing 'https' services, just NTLM.
This post helped me to work out what was going on: