Shoutbox

You shouldn't need to format to get Windows back. All you need to do is add a Windows entry to the config file for the bootloader.
For GRUB, the file is /etc/grub.conf (symlink to /boot/grub.conf IIRC).
For LILO, I'm not so sure, but it's probably in /boot.
Remember to get root permissions!