Just encountered this while attempting to call an 'https' web service that required NTLM authentication.

Exception text:

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

Solution:

Changed clientCredentialType to 'windows'. Do this in the app.config.

Changed from:

<security mode="Transport">
    <transport clientCredentialType="None" proxyCredentialType="None"
        realm="" />
    <message clientCredentialType="UserName" algorithmSuite="Default" />
</security>

To:

<security mode="Transport">
    <transport clientCredentialType="Windows" />
</security>

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.

Resources:
This post helped me to work out what was going on:
http://geekswithblogs.net/socasanta/archive/2007/07/06/113725.aspx