Okay... two things come to mind.
First, for some hardware providers the copy of Windows you have is eternally linked to that machine. You can't put in just *any* Windows CD and expect to be able to do anything. However, I've been able to get it to boot before I get that message...
Second, there must be something tripping the computer so it's not trying to boot from the correct CD drive. If it's a desktop, revisit the BIOS settings to ensure that it's booting from CD first. You can also try swapping the two CD drives and see if that works.
Finally, if you did get down to DOS, and you were able to get there with CD-ROM support, you can go over to that CD, type "setup", and let it run. That should let you do a repair install, or possibly even completely wipe and reload.
BTW, easiest way to format I can think of... get to DOS and run fdisk. Delete the partition and recreate it. Note that this isn't for sissies... it really will blow it away. But it can be fun....
