Assegure-se de que as máquinas não estejam lutando para serem "Master Browser" (verifique os logs de eventos do Windows para eventos que mencionam as eleições do navegador).
Se houver eventos sobre máquinas tentando se tornar o mestre, mas sendo rejeitado, isso pode ser o seu problema.
Escolha uma máquina (geralmente a mais strong) para ser o Navegador Mestre e, em seguida, em todos os outros, desative o serviço "Navegador de Computadores".