Também estou tendo problemas deste tipo. Vou descrever aqui a minha experiência com o Ubunutu em redes Windows nos maiores detalhes possíveis para ver se alguém identifica o problema.
Recentemente instalei o Ubuntu (versão 5.10) tanto em minha casa como no meu escritório. Em minha casa (todos os PCs com Windows XP) deu tudo certo e o Ubuntu reconheceu automaticamente todos os computadores (coisa que nem o Windows XP faz direito

:lol:).
Na minha máquina do esritório as coisas foram diferentes. Eu instalei o Ubuntu, depois o Ubuntu pediu para instalar o Samba e mesmo assim não reconhece os computadores. Quando eu entro na janela que dá acesso à rede Windows o Ubuntu pede um username, domínio e senha antes mesmo de aparecer qualquer coisa. Depois de tentar várias entradas, eu clico cancelar e na janela aparece o ícone da rede Windows, quando tento entrar lá, não acho nenhuma máquina.
Quando eu tento instalar uma impressora pela rede SMB já é outtra história... O computador acha sozinho todas as máquinas da rede e pede autenticação em todas elas.
Qualquer dúvida, pode perguntar, mas vai demorar um pouco para que eu possa respondê-las com ceteza, já que vou ter que reinstalar o Ubuntu (isso que dá não fazer backup dos arquivos de configuração...

:lol:)
Ah, sim, já estava quase esquecendo... Também não funcionou a configuração manual que foi sugerida acima.