DHCP problem

I have recently installed a firewall on our network and changed over to private IP addressing for our internal network. I have DHCP set up on our NT 4.0 Server to provide the addresses, gateway, DNS, etc. The problem I’m having is that the Win98 clients seem to lose their internet connectivity if I reboot the firewall which also happens to be their default gateway. All I need to do to get them back on the ‘net is run winipcfg and do release all and renew all. After that, they can surf away again. What am I missing in the DHCP setup or elsewhere that makes this happen? It doesn’t happen to all of the clients every time I restart the firewall, but it does seem to happen to all of them after one reboot or another. Any ideas?