Isso pode ser um problema de um mestre de navegador ausente, necessário para os computadores Windows.
Veja este artigo para obter explicações sobre os conceitos: Windows Browsing .
Se o computador Ubuntu for o principal navegador da rede, consulte Forçando o Samba a ser o mestre . As seções anteriores também contêm explicações dos conceitos envolvidos.
Se você quiser forçar os computadores Windows a não se oferecerem como navegador mestre, defina em HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Browser\Parameters
"IsDomainMaster"="No"
"MaintainServerList"="No"