Tú mismo identificaste el problema: LILO no puede hacer partir un Linux instalado más allá de los 1024 cilindros (creo que eso anda por los 5 GB, si me equivoco corríjanme).
Soluciones: instala GRUB (si usas una distribución moderna, debería estar en tu CD; si no, google es tu amigo
) o reparticiona todo tu disco duro para dejar la partición Linux (en realidad, sólo importa el directorio /boot) dentro de los primeros 1024 cilindros.
Creo que es obvio cuál solución es más fácil