I did manage a long time ago to fuck up a drive to the extent where fdisk couldnt do anything with it anymore ... had to get someone with a linux bootdisk to write 0's to the first couple of Ks of the drive (overwriting partition tables, boot records etc) before I could get MSDOS's fdisk to even format the thing.
So it might just be your partition tables which are FUBAR (maybe pqmagic can handle it, or otherwise use linux). Then the question remains how it got to that state, and wether it is a fault in the HD. If you can get the drive to work again after a proper formatting then there is a decent chance it wasnt.
Memory corruption could then be at fault, are you OCing?