1. implement dDNS on the network.
2. Modify the hosts files on all your machines
3. enable NetBIOS over TCP/IP in Samba
on all your Linux boxes. also look at nmbd
may be a bit lighter..
(I've never used option 3 I always go for option 1.. so I'm no expert on this one.. )
Option 1 is the best resolution, since both windows and Linux can query dns
Option 2, is OK but gets unweildy fast because you have to manually maintain all those hosts files. This is Why DNS was invented
Option 3 well if you really want to install and configure Samba on every Linux box in your network..