Comment 29 for bug 316862

Recent experience with the network leads me to believe that this is, at least in part, a Windows Browser-Master problem.
Windows is known to have trouble (some say it's broken) with browsing peer-to-peer networks. One computer in the network takes the role of being a browser master. There is a defined hierarchy of who does it - generally the machine that is on longest but has the more recent operating system. The browser-master is the machine that stores a list of host names and their ip addresses, enabling browsing of the network. I think that Linux machines on a Windows network rely on the Browser-Master for browsing.

Setting up a Windows computer as a broswser-master is inaccurately and incompletely documented and supported by Microsoft, who really you to have a Windows server. My experience that the process of a browser election can be completely confused if other machines are on the network, leading to unreliable browsing with both Windows and Linux. In particular it may be that a non-Windows DHCP server inhibits Windows machines from being browser-masters.

Browsing problems on our network seem to have disappeared since we've installed an SME server (www.contribs.org) AS A DOMAIN/WORKGROUP CONTROLLER. This has resolved our browsing problems.