Supongo que al reinstalar no habrás tocado nada de particiones, así que seguirás teniendo tus particiones de linux.
Mete el CD1 de MDK, arranca, en el menú que te saldrá pulsa F1, escribe rescue y en el menú siguiente tendrás una opción de recuperar el sector de arranque.
PD: Lo digo de memoria, pero más o menos era así. Si no estás seguro, buscando "rescue" fijo que salen más hilos.