Ok, usually that points to incorrect DNS configuration, can you describe how you've set up DNS on your network:
Do you have the ISP's DNS server listed in the external adapter of the WinGate server?
Do the clients have their DNS server pointing at the WinGate server?
Are you running Active Directory, or are you running another DNS server on your network?
Can you ping a web URL from the client machines? Try
www.google.com. Can you ping this address from the server?