Hmmm, that's odd that you're getting that problem. Go to <A HREF="http://www.bootdisk.com" target="_new">bootdisk.com</A> and get a winME startup disk. Boot from that, type fdisk at the prompt and delete your partition from there. Then reboot, take the floppy out and put the cd in. You should be good to go from there.
Some day I'll be rich and famous for inventing a device that allows you to stab people in the face over the internet.