SOunds like the partition table might be hosed up. If you can afford to zero your drive then do a:

dd if=/dev/zero of=/dev/hda

Then repartition- you shouldn't get that error anymore.