Samba shows on some machines but not on the others

[Erno Soinila]

1 Samba( Mansku = M ) server on Red Hat Linux
4 Windows PC:s :
1 W98 ( Hietsu = H)
1 Windows Me (Lonkka = L)
2 DualBoot Windows 2000 & Me (Aleksi = A, Flemari = F)

Problem is as far as windows is concerned on A and F machines the Samba
server does not exist. Windows cannot find the machine. However using
smbclient from the samba machine allows to use all the machines. Also All
Windows machines find and happily use each others. Machines L and H happily
use the Samba server. Also Machines A & F used to find Samba just fine until
some time ago( with no noticiable event that might have caused it).

What could be the problem and how could it be fixed.
-----------
Erno Soinila
esoinila at elmorex.com