I have found in the past, that on occassion of formatting with a few *nix file systems, that if they had a different file system on it previously that was *nix based and not removed prior to attempted install that they would boot just like you stated. Would wind up having to do an fdisk /mbr to get rid of LILO, delete all of the partitions on the drive, affectivly leaving it blank. and then try the install. Another one that I had that was similar was using two differnt drive controllers for primary and secondary. Went to a dual controller and it was fine.
