Si instalaste desde CD suelen tener una opción "rescue".
Otra opción es arrancar con una knoppix, montar la partición de linux y ejecutar el lilo indicándole dónde quieres instalarlo (si es en el mbr del disco maestro del primer ide sería /dev/hda)
Un saludo