Hmm. This is odd. Technically, GRUB should have been overwritten with the Windows Boot loader. Anyway, GRUB is probably confused because of your OS restore. Um, the best thing I can offer is to try this: https://help.ubuntu.com/community/Boot-Repair#A1st_option_:_get_a_CD_including_Boot-Repair
If Windows has a proper presence on your hard drive(s), using this tool should allow GRUB to fix itself and add it back to the boot menu. Otherwise, you will need to do a clean (read: install windows from scratch, NOT FROM A RESTORE DISC), make sure you partition enough space for both Win and Ubuntu, and then install Ubuntu once your windows install is complete.
*Not sure If I can put this here, so remove if it violates rules (which it might, sorry)
If you only have Windows restore discs, like the ones that come with the computer, you can obtain a new retail disc image using bit-torrent. As far as I know, as long as you download the same version of windows for which you have a product key for, It's technically not illegal. Anyway, I have a feeling this is violating rules. if it is, my bad, and please edit,