One thing to check is that the nmbd service is running. It handles NetBIOS over IP naming services to clients. You haven't indicated how your network works. There are different technology families for different versions of Windows. The NT/WINS type networks work very well with samba. Samba can replace any windows server or domain controller. If the network uses 2003 / Active Directory, then samba can do some things and not others. One solution is to use OpenLDAP instead of an Active Domain server. ( An AD server is a smb'ified LDAP server solution.) LDAP is more general. Also, Windows XP Home is crippled and can't join a domain or use Single Sign on in a NT or AD configured network. I never had problems browsing before XP came out. XP computers may not use netBIOS over TCP unless you enable it. It uses TCP/UDP instead of the LLC layer broadcasts to locate other hosts. If you have a mix of technologies, this may be the problem.
There are a couple of books you can download from the samba.org website: "Samba 3 Reference" and "Samba 3 By Example". You may also have these books in /usr/share/doc/packages/samba/ if you have the right package installed. SuSE and Fedora Core have these packages. In SuSE, the books are in PDF format. If memory serves, FC 5 has them in Postscript format.
Another thing to check is that you don't have the ports you need closed. The nmbd manpage indicates that if you have samba running as an xinetd service, then you need to have these config files properly configured:
If the server is to be run by the inetd meta-daemon, this file must
contain suitable startup information for the meta-daemon.
or whatever initialization script your system uses).
If running the server as a daemon at startup, this file will need to
contain an appropriate startup sequence for the server.
If running the server via the meta-daemon inetd, this file must con‐
tain a mapping of service name (e.g., netbios-ssn) to service port
(e.g., 139) and protocol type (e.g., tcp).
Also, read through the man pages for smbd, nmbd, and smb.conf.
Also, for the source reference for NetBIOS, you can enter "rfc:1001" in the konqueror browser, or download it from: http://www.ietf.org/rfc/rfc1001.txt
There could also be an oddball problem. For example, if an old Windows98 host has a netware protocol installed, it will win browser elections. The samba books I mentioned will cover this.