If both your client and service is installed on the same machine, and you are facing this problem with the correct (read: tried and tested elsewhere) client and service configurations, then this might be worth checking.
Check host entries in your host file
%windir%/system32/drivers/etc/hosts
Check to see if you are accessing your web service with a hostname, and that same hostname has been associated with an IP address in the hosts file mentioned above. If yes, NTLM/Windows credentials will NOT be passed from the client to the service as any request for that hostname will be routed again at the machine level.
Try either of the following
Edit: Somehow the above situation is relevant on a load-balanced scenario. However, if removing the host entries is not possible, then disabling loop back check on the machine will help. Refer method 2 in the article https://support.microsoft.com/en-us/kb/896861