Dual-booting, unable to format

[AliveUD]

I've been dual-booting Debian and Win2k for a while now and am loving it. However, I just upgraded my box to 64-bit and I need to reinstall both Windows and Linux. Normally I install Windows first and then let Linux overwrite the MBR to take control and allow the dual-boot. But it seems that my Win2k Setup CD is unable to undo what the previous installation of Linux has done to the drive and now I can't install Windows :( Setup keeps telling me that it gets to 100% formatting the desired partition (no matter where on the drive I try to make it) and then says it was unable to format; which leads me to believe that it's the boot sector or MBR that is messed. I am able to use fdisk to format the drive with no issues and have been able to format the desired partitions from within Windows by plugging the drive into a spare machine. I was also able to use a Win98 CD to write a new MBR and a new boot sector, but neither seemed to solve the issue.

Please help, how can I go about reinstalling these two operating systems?