BIOS must be set to boot to CDRom.
Additionally, since there is an installed OS on your hard drive, you must press a key during the boot when it asks you to do o or it bypasses the CD and goes to the HD anyway.

Once booted on teh CD you can delete the partiton and start over.