Bom, depois de muito pesquisar na net, testar muitas das coisas que li, finalmente encontrei o "algoritmo" para recuperar o GRUB (Grand Unified Boot Loader) perdido quando instalei o windows em uma máquina que já tinha o linux.
É bom deixar claro que quando digo "GRUB perdido", quero dizer que o grub não está mais na MBR (Master Boot Record), ou seja, não é o gerenciador de boot padrão no computador.
A distribuição que eu tinha instalado nas máquinas (sim, testei em duas máquinas que estavam nessa situação e advinhem? FUNCIONOU!!) era o Ubuntu 9.04, mas para fazer esse procedimento, utilizei o live-cd do Ubuntu 8.10 que também tem o grub.
Vou descrever como fiz.
1. Coloque o live-cd do ubuntu no computador e escolha a opção "Testar sem instalar" (ou algo semelhante. Não lembro a mensagem exata agora).
2. Abra a console e digite os comandos abaixo na sequencia exibida e verifique se as respostas aos comandos estão de acordo com as observações feitas:
2.1. $ sudo grub
OBS: O inicio da linha irá mudar do simbolo '$' para 'grub>'
2.2. find /boot/grub/stage1
OBS: Nao lembro bem, mas parece que nesse etapa você estará procurando em qual HD e partição o grub foi instalado. A resposta será algo do tipo "(hd0,1)" ou "(hd1,6)", que é o que vc irá utilizar como parametro na proxima linha.
2.3. root (hd0,1)
OBS: a parte "(hd0,1)" deve ser igual a saida da linha anterior.
2.4. setup (hd0)
OBS: "(hd0)" é parte do que foi digitado anteriormente, ou seja, é a partição onde está instalado o grub.
2.5. quit
2.6. reboot
Resumindo:
2.1. $ sudo grub
2.2. grub> find /boot/grub/stage1
2.3. grub> root (hd0,1)
2.4. grub> setup (hd0)
2.5. grub> quit
2.6. $ reboot
Boas explicações sobre o GRUB