hmm...first let's try this:
1) boot with your windows cd/bootdisk, that has fdisk in it (cd is good I think - 'boot computer with cd support' or something is the right choise)
2) from the command prompt run fdisk
3) if it asks you something about big harddrives or something, hit yes
4) see if fdisk can see all your partitions. if it does, simply delete them all and create new one(s) - REMEMBER to make one partition ACTIVE or you can't use your HD to install anything

after this you can jump the next sections to the part "WHEN DONE" which is further below....
now - if fdisk can't see your linux drives, which is possible, get your linux running. find it's partition program, I guess it's called fdisk too, and start it (it should be in /sbin/fdisk). now:
1) you'll only need console for this. start fdisk like this (don't write $ or # because they only indicate command prompt signs here):
$ su
<type root password and press return>
# fdisk /dev/hda
(Command below means the command prompt of fdisk. so on the next command, just press m)
Command: m
(now you'll see a help list)
Command: p
(now you'll see your partition table)
Command: d
(it asks you the number of the partition, you'll see the numbers in the partition table above like hda1 hda2 hda3 etc. - the numbers correspond them like 1, 2 and 3)
Partition number (1-5): 5
(you might have a different number of partitions, but just select the last number and after it just hit d again and give new number until all of them have been removed)
Command: w
(this WRITES the changes and exits! BE SURE YOU DID EVERYTHING ALLRIGHT)
2) boot your PC with Windows install disc and start windows's fdisk
3) create the partitions you need with it and then set the 1st primary partition ACTIVE.
4) after you're done, quit and reboot with windows installation disc
:::WHEN DONE:::
-> after booting with windows install disc, install it. HD erasing should work.
WARNING: using fdisk (either windows's or linux's) means that you really REMOVE or EDIT your partitions! the changes you do CANNOT BE RECOVERED after you've WROTE THE CHANGES! so if you want something to be saved, do it before fdisk.