Make sure that your machines DNS settings go to the gateway, not your upstream providers DNS servers. If you've been setting the IP's statically you may have set it to something other than your gateway. In fact, you most likely have. You'll need to change /etc/resolv.conf if you have.
I've used small bind installs on a fair number of systems now, and honestly, they are dirt simple. I'd suggest following a guide like that and posting to the list if you have an issue with anything specific. I know most people at MUUG who run DNS servers run Bind, or are very familiar with it, so we'll be able to help you out.
Another option: If you know which MAC addresses go to which machines, you could setup a small DHCP server and have their addresses set in /etc/dhcpd.conf. This would allow you to change the IP range fairly easily, and also push custom DNS options down without having to touch each machine.
Following on Rob's suggestions, I would recommend combining those two functions into one by using dnsmasq (http://thekelleys.org.uk/dnsmasq/doc.html). This software is used successfully on many small firewall distros and is in fact embedded in many home routers. Its primary advantage is simplicity, compared to an integrated DNS+DHCP setup using BIND and DHCPD, but the fact that it also captures DHCP machine names might be a substantial benefit in Dan's situation. It additionally uses /etc/hosts on the firewall/gateway as an additional source of names, so you don't have to configure multiple name databases. Its big downside is the lack of flexibility - it's designed to solve a small handful of use cases, and it does those very well, but it can't do everything BIND or DHCPD can do.
On a related note, if you're interested in using commodity hardware to run a firewall/router/gateway/DNS server/DHCP server/proxy server, and your objective isn't specifically to learn Linux, I would recommend pfSense (www.pfsense.org), which is based on FreeBSD, and integrates all the common use cases into a fairly clean GUI. (FYI, I'll likely be doing a presentation on pfSense at a meeting sometime this year.)
-Adam Thompson athompso@athompso.net