1.Follow mcleodnine's advice first.
2.If both Partition Magic and the Redhat installer are giving you the same message, you should probably do a low-level reformat (provided no data that you care about is on the disk, because it will be wiped). Before you do that though, try using the fdisk utility. If it recognizes the drive's partitions at all, delete them, save the changes, and reboot. This will rewrite the partition table, and if it works, will take much less time than a full low-level format.