Também tive esse problema, depois de formatar o windows perdi o grub, e pesquisando na web encontrei um link que me ajudou bastante.
Se você perdeu o boot do Grub ou simplesmente instalou o Window$ depois do Linux, certamente perdeu o dual boot proporcionado pelo Grub. Para recuperá-lo, siga os passos abaixo.
Os sistemas operacionais instalados na máquina foram o Ubuntu 7.10 e o Window$ XP.
Primeiro, inicie o Ubuntu pelo live cd
Abra uma sessão de terminal e digite o seguinte:
sudo grub
Você cairá no shell do Grub….nele, digite o seguinte:
find /boot/grub/stage1
Esse comando irá mostrar onde o Grub encontra-se instalado. No meu caso ele está no (hd0,1).
Digite a seguir o seguinte comando, substituindo os valores 0 e 1 pelos exibidos no comando anterior, caso seja diferente.
root (hd0,1)
Após, instale o Grub com o comando
setup (hd0)
E saia do shell do Grub
quit
E reinicie a máquina
Pronto. No próximo boot você cairá na tela do Grub.
Fonte:
http://infoclic.com.br/