What is doing your DHCP?
Do you have WINS running?
How about local DNS?
Is Samba running on either Linux box?
One solution to this type of problem is to run
dnsmasq --
Description:
http://www.linux.org/apps/AppId_6060.html
Homepage:
http://www.thekelleys.org.uk/dnsmasq/doc.html
It allows your to have a "master" hosts file on the (local) DHCP/DNS server -- it simply uses its own hosts file as part of its DNS resources.
It also allows domain-by-domain, blocking of adservers &c via its
dnsmasq.conf, contrasted to host-by-host blocking using
hosts. With folks like erasercash(.com) pushing 1000 hosts, this is a welcome simplification.
Another solution
may be to have Samba do WINS. Never done that, just heard of it, so I can't be of much help if that's what you need.