This is a NetBIOS browsing issue. If you look at your Windows logs you will see messages about browser elections etc.
If there are Samba machines and they are badly configured, it will hose your Windows networking. All Samba machines should have OS_LEVEL=0 to prevent them from interfering with Windows NetBIOS browser cooperation.
You also should never run a Windows server-based network without a WINS server active.