I'm really keeping you guys busy this week ;) Thanks for all the help!!!
I have all my Wingate services setup to use the system policy. The system policy is set to use the NT user database on windows SBS 2003. I changed the policy to only grant usage rights do Domain Users and Domain Admins.
At first this works OK, but after rebooting a client, I start getting a message on the client saying something like "you don't have permission to use this". When I go look in the GateKeeper I see Authentication failed messages for user NUANDA$. I don't have a user NUANDA$. Nuanda is the name of the client machine where the error is occuring. On the Users tab - User list - I now see a NUANDA$ user. If I synchronize it goes away.
After a while, the client gets properly authenticated using NTLM.
Very strange