Re-reading this post, and from experience I had in the lab today...
When using the proxy directly from a client machine, it was not passing on the NTLM authentication properly (for a MS SharePoint server). What we had to do was use NAT, with transparent proxies (intercepts).
So in the case I had in the lab today, I had to do as follows.
1. Open Internet Explorer, and set it not to use a proxy server. You "may" also want to set the security settings to prompt for a username and password. (IE --> Tools Menu --> Security tab --> Custom Level --> Scroll to the bottom and select under the label "User Authentication" --> Prompt for Username and Password)
2. Check NAT was installed
3. Set the client computers TCP/IP settings to utilise NAT
If WinGate Server internal TCP/IP settings is:
192.168.9.1 / 255.255.255.0
Then WinGate Client TCP/IP settings is:
192.168.9.2 / 255.255.2555.0
Gateway and DNS 192.168.9.1
4. Then turn on intercepts in the WWW Proxy service
GateKeeper --> Services --> WWW Proxy Service --> Sessions
Then try again.