OK, so when using DHCP you can resolve IP addresses?
If so, then it's not DNS, it's a routing issue. Check the gateway that your clients are using. (try IPCONFIG at the command prompt) The gateway should be router / firewall / modem - whatever the internal IP address is of your internet connection.
(E.G. we have a firewall, and a modem from the firewall that then plugs into the phone line for our ADSL. We would use the IP address of our internal port on the firewall. The firewall will route the traffic to it's WAN port, then the next hop is the LAN of the modem. The modem routes to the WAN which is the ADSL circuit)
If you're still not too sure. On your DHCP client, type in the following at command prompt:
route delete *
route add 0.0.0.0 mask 0.0.0.0 x.x.x.x
the x.x.x.x is the IP of your gateway. E.G:
route delete *
route add 0.0.0.0 mask 0.0.0.0 10.3.1.254
(If 10.3.1.254 is the internal IP of your router/firewall)
Then try another TRACERT
and see where it goes.
If that's working then you need to change the settings on your DHCP server to add a default gateway that is valid and correct.
If you need more help let me know and i'll try to explain it a bit better!
Good Luck,
Steve.
"They have the internet on computers now!" - Homer Simpson