[Samba] Netbios name resolution with DHCP

[Robert Wood]

I have a network with RH7.2 (netbois name "server"), Mandrake 8.1 
("Linuxbox"), Smoothwall ("Smoothwall"), WinNT ("di-bosco"), Win 98 
("robertw" & "Nicole") x 2 and Win 2k ("DiBosco2k").

Smoothwall is the DHCP server.

Why would it be that all the Windows machines can ping to a netbios name, eg 
ping server, ping Linuxbox etc, but non of the Linux based machines can? 
Linux machines all say

unknown host machinename

What do I have read up on to make this work on the linux machines as well? 
All the machines bar Smoothwall and RH server are dynamic IP addresses, I am 
under the impression this makes things somewhat more complicated!

Cheers,

Rob