Após instalação do Windows o Grub some?

Simpler e eficiente, muito bom...

O comando gub-install também quebra um galho nesta ;)
Muito bom...

eu costumo usar a seguinte sequencia:

# grub-install hd0
# update-grub

ele auto-detecta os sistemas instalados e gera o menu.lst; bem prático....

uso ele pq sempre faço mudanças no hd e o grub antigo "perde a validade"

Também uso o Ubuntu 8.10 e uma vez tive que formatar o Windows. Usei essa dica e também deu certo!

"Com um LiveCD do Ubuntu abra um terminal (Aplicações -> Acessórios -> Terminal) e digite:
1 - sudo fdisk -l
Você verá com este comando todas as partições disponíveis no seu computador.
Agora monte a partição que possui o seu Ubuntu.
2 - sudo mount -t ext3 /dev/sda5 /mnt
NÃO esqueça de trocar ext3 pelo tipo de partição (reiserfs, ext2, ext3, xfs) e sda5 pela
partição onde você instalou o Ubuntu!
Com a partição montada, chega a hora de recuperar o Grub
3 - sudo grub-install --root-directory=/mnt /dev/sda "

Uso Ubuntu e tive problemas com o grub. Usei esta mesma sequência, mostrada também pelo Morimoto. É a única que funcionou. As outras dicas dadas nos comentários não funcionaram.

Parabens pelo post Rafaell funcionou seguindo exatatamente na ordem como especificou!