You should try a liveCD first. Ubuntu for example. Write it out / copy it to a pendrive. Boot it, and check your partitions by opening a terminal and typing:
sudo gparted
Here you can create a new partition table. (You'll lose all your data!). Try creating one ext2 partition for example which covers the whole HDD. (In the Fedora installer you'll make your partition setup what you want, this is only for the sake of being detected.)