The problem lies in the Harddisk geometry the BIOS passes to the LILO loader. Unfortunatly, when booting from a normal install, you sometime get your Harddisks parameteres read in LBA, CHS or Large form, this due to the new read of the Partition tables when you changed the partition informations. If the BIOS gave in the harddisk geometry data in LBA, the system will reread the Harddisk geometry in CHS mode, thus the boot will fail.

So, to get this working right, go into the CMOS Setup of your Mainboard, and play around with the Translation Method. Mostly after this error to happen - LARGE or CHS will fix the problem.