I had to set up a similar setup for my home network, ended up using a free OpenDNS instance for the DNS service since I didn't feel like setting up a full dns server. NAT is pretty straightforward with Windows 2000 Adv Server though. Did you run into any specific issues with setting it up?