(Ответ от оригинального плаката, но не в том месте, тронутый мной.)
Привет всем, я наконец-то решил свою проблему, добавив эти 2 строки в мой код клиентского приложения:
WindowsClientCredential wsCred = wsFactory.Credentials.Windows;
wsCred.AllowedImpersonationLevel = TokenImpersonationLevel.Impersonation;
Эти 2 строки заставляют клиента выдавать себя за каждый раз, когда он подключается.