Few days ago I had quite a headache with authentication problems when using Windows authentication between client and wcf web service. The error I was getting was "The HTTP request is unauthorized with client authentication scheme 'Negotiate'. The authentication header received from the server was "NTLM". None of the solutions on stack worked because most of them were related to old methods.
THE ANSWER: The problem was all of the posts for such an issue were related to older kerberos and IIS issues where proxy credentials or AllowNTLM properties were helping. My case was different. What I have discovered after hours of picking worms from the ground was that somewhat IIS installation did not include Negotiate provider under IIS Windows authentication providers list. So I had to add it and move up. My WCF service started to authenticate as expected. Here is the screenshot how it should look if you are using Windows authentication with Anonymous auth OFF.
You need to right click on Windows authentication and choose providers menu item.
Hope this helps to save some time.