The reason to the situation is this: Grub is installed (unless you manually made it different) to the MBR (master boot record) of the harddisk, the place where BIOS looks for bootloaders. Actually in Grub's case there's a part of it (stage1) and part of it is stored into the /boot partition of your Linux distribution (stage2). Mainly the necessary parts are in MBR, configuration files are read from the disk (compared to LILO, which is completely in MBR, but is not as dynamic to configure, for example). Now when you reinstalled your Windows, it didn't ask you if you want to install a bootloader, it did it without asking - installed the Windows bootloader, which is also installed to MBR. That means it overwrote that part of Grub that was in MBR. Your Linux installation is perfectly safe, you just can't boot into it without a boot disk
Well, have you got the Ubuntu Desktop disc still somewhere? If yes, then that does. It's a live-cd you can use to boot. After you boot, you can mount your harddisk-Linux-partitions and use chroot to change the working root directory to be "in the harddisk" rather than in the virtual filesystem created to RAM when running the live-cd. There are detailed instructions about this procedure on the web, so read those. After that you can reinstall Grub (using 'sudo grub-install /dev/sda' if /dev/sda was the harddisk whose MBR you want to write Grub to - primary SATA drive, for example), and add your Windows boot section to /boot/grub/menu.lst (or just run 'grub-update' to have it search it automatically), reboot and enjoy your life again.
The "tricky" part in that is, after booting the live/Desktop cd, to change the environment so that the Grub installation is made to the disk, working in the harddisk's filesystem, and not in the virtual filesystem of the live-cd. But like I said there are good detailed instructions on how to reinstall Grub using a live-cd on the net.
Reinstalling whole Ubuntu is a bit overkill..all you need to do is get the MBR "fixed", the first 512 bytes of your harddisk. Actually it's a good idea to make a backup of your MBR when you have it still working; create an image file, which you can later easily push back if you happen to mess up your MBR. Provided that partition information has not changed after the MBR mess-up (you haven't deleted/resized any partitions) you can just copy the small image back and reboot. Using 'dd' command in any Linux live-cd and maybe a USB media to save the image file on this is a real lifesaver..