Bom, já encontrei diversas dicas de como restaurar o LILO, mas para quem usa o Slackware e ainda tem o CD de instalação, tem uma forma fenomenal...

Primeiro dê o boot normalmente pelo CDROM do Slackware e vá até a parte que ele pede pra fazer o login. Lá você entra como root normalmente.

Agora vamos passar a perna no programa de instalação, entre com os comandos:

# rm -R /boot
# mkdir /mnt/temp
# mount /dev/hdxy /mnt/temp (substitua hdxy por sua partição Linux)
# ln -s /mnt/temp/boot /
# lilo -C /mnt/temp/etc/lilo.conf

Agora é só reiniciar! Acredito que essa dica valha para outras distribuições.