If you pop your Linux CD in at boot, most distros have the option to boot installed system. If you let us know what distro you have, we could point you in the right direction. It's then a case of re-installing the Linux bootloader to get your menu back.
Whenever you re-install Windows, by default it writes its own bootloader to disk which doesn't take into account other OS' such as Linux. You shouldn't have lost your Linux data, so don't worry