Whenever it's visibility of machines with Windows file sharing, 90% of the time it is what I've described above -- it's neither Samba nor Gnome's fault. The best thing you can do for the browsablity of your network (once you've ensured that NetBuei isn't in use), if you have an always on non-Windows machine (anything that will run Samba), is run Samba on it with nmbd enabled, even if you don't share anything from that samba instance itself. By default, Samba will always win network elections to become the master browser. Since it always wins, the list of hosts that are sharing is more consistent. Obviously, if you want to access shares on a machine that isn't always on, it takes a while (about 30s or so) after that machine boots to show up in the browse list reliably.

Another thing, if you have a bridged network, with both wireless and wired segments (which might be the case with a media player PC), run samba/nmbd on the wired segment. If a wireless machine that is the master browrser loses connectivity, a network election might need to take place and different machines might become the master browser, and they don't always have the full list of machines all the time.