My favorite answer on these forums:
www.killdisk.com
This ute will write zeros to your hdd, making it as close to "new" as possible. Then, reinstall the OS like normal.
In my experience, sometimes viruses or corrupt WIN files are reinstalled if you simply fdisk. Fdisking deletes the file system, not the files.
You didn't mess with the HDD jumper setting, did you?