I had this prob on some obscure distro I was playing with and I seem to remember it had something to do with where the linux partition was placed on the hard drive, I had muliple partitions on 2 different drives & lilo wanted linux to be on the first hard drive in a partion with a starting address of less than 1024 -- err cylinders I think, not MB, not sure --
think this was an old Caledra distribution with a pre 2.0.0x kernel on a 386 though so what do you expect???
I got a list of LILO hang ups
...somewhere...