Sounds stupid...
But when I had HD with formating issues (which was a long time ago, everybody will suggest you change your disk...), when I had problems, I just use a partition tool to format with Linux, then Windows, then Linux swap, then delete the partition... Go ahead, do whatever, formating in different system files (NTFS, FAT, FAT32, ext3, ext2...). Sounds stupid, but it worked more than once...