Existem várias coisas que podem ser a causa disso.
Às vezes, demora um tempo para as máquinas se encontrarem com o NetBIOS, se é isso que você está usando. Este é geralmente o caso se você não tiver um controlador de domínio.
Veja também o link
Configurando seu servidor samba como um servidor WINS, e usando suas máquinas Windows, isso pode ser uma maneira de corrigir isso.