Try putting entries in the /ETC/HOSTS file on the server for your client machines.
Or ... and I have never tried this.. but try "joining" the NT domain that you created with your Samba server. Do this in the network properties of the Win9x clients.
If SAMBA is working right, the Win9x clients will think they are joining and NT domain. You will need root login credentials to do so I believe.
I need to check my Samba book at home: