You may need to do a "Low-level format" You should be able to get one
of these apps from your HD manufactorer for dos, but sometimes they can
be a pain. A low-level format brings your harddrive essentially to the
same as when it came out of the factory. If you HD maker doesn't have
a low-level format, go to Maxtor, they do, and it doesn't matter what
brand you use.

You could also try GNU Parted. Get it from GNU here:
http://www.gnu.org/software/parted