Sembra il classico dramma dell'elezione del master browser. Il metodo di individuazione dell'elenco dei computer (perchè da quanto scrivi intuisco sia questa la domanda) di microsoft è complesso e cervellotico a dir poco (anche per motivi di compatibilità storica).

Ci sono essenzialmente 4 "livelli" diversi
1) "sfogliare la rete" => qui tipicamente è il problema dell'elezione
2) richiamare con un nome CIFS un host (es. start=>esegui=>\\computer\condivisione) => qui la lentezza può dipendere da un server wins (vista) che fa a cazzotti con il client samba

Nel primo caso puoi, spudoratamente, editare l'smb.conf per dare un privilegio smodato alla macchina linux durante l'elezione.