You are probably way ahead of me but I remember getting that error under 2 conditions (I think). 1. If the geometry of the disk didn't match its real geometry or the boot partition went past the 1024 sector (although it is supposedly possible to fake out the boot proms according to a little pamphlet by Matt Welsh that came with the old Infomagic CD set.) 2. If I installed a new vmlinuz without rerunning lilo.
Good Luck, Nathan