OK I would like to try the FDISK thing. Is there instructions on how to do what you said evil_fantast?

Boot your pc in DOS from a startup disk or your bootable me installlation cd. then run fdisk and erase your primary boot partition. Reboot and run fdisk again. Create a new primary partition. Set it as active partition and exit fdisk. format this new partition (Should be the same drive letter it was initially) and run windows setup again.