I've encountered the same issue once. It was resolved by using a linux boot disk and re-installing lilo. I think in your case (Fedora) uses Grub as the linux loader.