W2K NAT/ICS Help.

I am tring to get either full nat or ICS to work on a win 2000 server (SP1). My clients are winnt wrksta 4.0 and win98. The server can connect to the internet however all clients get a dns error when trying to get anything on the internet. I’m using a 56K modem as a demand dial interface, i’ve tried NAT with the DHCP allocator and with a full dns and dhcp server using active directory. Plain ICS produced the same results. Please help….