Um dos grandes inconvenientes da reinstalação do famigerado windows é que perdemos (momentaneamente) o acesso ao linux.
Para corrigir, faça o boot com um live-cd do linux, abra um terminal e execute (como root ou usando sudo):
mkdir /media/mnt
mount /dev/sda1 /media/mnt/
mount -o bind /dev/ /media/mnt/dev
Isso irá montar a partição linux em /media/mnt. Execute então:
chroot /media/mnt
para entrar no ambiente do linux já instalado.
grub-install /dev/sda
fará a restauração do grub (considerando sda como disco de inicialização)
Testado com ubuntu 9.04 e winxp.