1) Os outros computadores estão compartilhando alguma coisa (alguma pasta ou uma impressora)? Se não estiverem, você provavelmente não vai conseguir localizá-los.
Eles possuem pastas compartilhadas, mas eu não consigo nem enxergá-las.
2) Windows Vista e 7 têm uma configuração para impedir que os computadores sejam localizados na rede. Se você quer localizar computadores com esses SOs, você tem que desativar essa configuração.
No caso, nem o Windows XP consegue ser visto pelo Ubuntu.
3) O Firewall dessas máquinas pode estar impedindo a você de conectar-se com os serviços da Rede Windows.
Não creio que seja isso, pois ás vezes o computador que tem Win XP aparece na Rede, porém ele não consegue montá-la. Mas quando isso acontece, de vez em quando eu consigo acessá-la digitando o endereço IP local da máquina WinXP, porém outras vezes não.
Os PCs Windows se comunicam entre si sem problemas, porém no Ubuntu eles nem aparecem.