First, your "distribution" setting (in the left panel of your post) claims that you're running an old, unsupported, Fedora release. (The oldest supported Fedora release is Fedora 12. And that for only a few more months.)
Second, rather than wiping/reinstalling, boot from a current Fedora installation disk and select the "linux rescue" boot option, do the suggested
chroot and run
grub-install. That should get you back up and running.
I think that the problem you're having is that GRUB is looking to boot from a partition that you've moved, since the GRUB MBR (for the old GRUB format used by Fedora) stores the physical boot partition information in the MBR. (The newer GRUB2 lets you use the UUID of the partition - among other things - in addition to the physical partition information.)
<edit>
Oh, to answer your original question, download and burn, for example, the
SystemRescueCD, boot from it, and run
parted on your hard drive. Enter the help command to see a list of options, and select the one to create a new DOS partition table. Then exit with write, and you'll have a wiped disk.
</edit>