hostname resolution in a mixed network

I have an 8-port SMC router (SMC7008ABR) acting as a DHCP server for my
home network. However, I notice in the Status screen that it only
displays the host names for my Windows boxes and not my Debian Gnu/Linux
boxes.

A more serious problem is that my Linux boxes don't seem to be able to
resolve the names of my computers. I can't ping them by host name. I can
ping all the computers by host name from my Windows boxes however.

My setup is a little complicated in that I have a W2K DC which of course
needs to have DNS turned on to operate properly. It's possible that it
is providing the name resolution for the XP boxes.

I've tried setting up a Linux DNS server. It works but I can't seem to
get the other boxes to use it. If I directly modify /etc/resolv.conf on
a Linux box to point to it, resolv.conf gets overwritten when I restart
the network interface.

Any ideas on how I can get this to work?