Generally I've done it the other way around -- Windows then Linux. Put the OS that understands the others on last.
This is how I repair GRUB after ghosting a Linux box at work; it's written using a Gentoo install CD to boot from and with an install of Debian on the hard drive, but it should be relatively generic. It assumes certain things about partitioning; you should make sure you have written copies of /etc/fstab and /boot/grub/grub.conf (or wherever they live on your box) to refer to before you start.
Click here to view the secret text
×Boot from a Gentoo installation CD.
Mount the hard drive volumes:
mount -t ext3 /dev/hda5 /mnt/gentoo/
mount -t ext3 /dev/hda1 /mnt/gentoo/boot/
mount -t ext3 /dev/hda6 /mnt/gentoo/usr/
Chroot to the hard drive installation:
chroot /mnt/gentoo/ /bin/bash
Run GRUB (one of these should work, the other will do no harm):
grub
/usr/sbin/grub
Reinstall GRUB:
root (hd0,0)
setup (hd0)
quit
Exit the chroot jail:
exit
Reboot from the hard drive:
reboot
Log into the main Linux environment as root.
Reinitialise the swap partition:
mkswap /dev/hda9
Reboot to make the new swap area available:
reboot
Once you have GRUB back in place your machine will be back to a single-boot Linux box, but then you can add the Windows partition to grub.conf and get dual boot working.