Are some of your machines connected wirelessly? If so, then you might have a bug where multicast isn't working reliably on some machines, breaking multicast protocols like Bonjour, and broadcast protocols like NetBIOS name service.
Make sure your multicast rate isn't set too high on your 802.11 Access Point. It has to be at a "lowest common denominator" rate; a rate low enough that all clients can receive it reliably no matter how far they are from the AP.
Also, try this test: temporarily turn off wireless security and see if the problem goes away. If it does, that's a good sign that either or AP or one or more of your clients isn't doing 802.11 multicast encryption correctly. Sometimes you can resolve this by switching from a more complex wireless security mode to a simpler one. For instance, WPA2 "Mixed Mode", where both AES-CCMP and TKIP encryption are enabled, is more complex because the multicast cipher type can be different from the unicast cipher type. Switching to pure WPA2 (AES-CCMP only) is simpler because it uses the same cipher everywhere, and as a bonus, it's more secure.