Internet Connection Sharing in W2K

I have been trying to enable ICS on a Windows 2000 Workstation. The W2K System can then still connect browse fine. Clients get an IP address, but when browsing make no progress after the URL is resolved. I have seen this before when the Gateway is set wrong, but the clients seem to detect the gateway correctly. Pinging the Gateway times out. This fails with a variety of client OSes (W2K and Win9x). I thought it might be a security issue, but cannot find anything that would be affecting it. IPSec is not enabled. My firewall does not appear to be the problem either.