I had exactly the same issue last week - WCF program behaves strangely on one server - why?
For me the solution was rather simple. Sharepoint has its own set of permissions. My client tried to log on as a user that wasn't explicitly given access to the webservice through Sharepoint's administration panel.
I added the user to Sharepoint's whitelist and bang - it just worked.
Even if that isn't the issue, please note that
The HTTP request is unauthorized with client authentication scheme ‘Ntlm’. The authentication header received from the server was ‘NTLM’.
Means (in English) that you simply don't have permission. Your protocol is probably right - your user just doesn't have permissions.