WIN installation won't start on a new PC

The plot: in BIOS I set CD as first boot device, but not one (of 3 – XP SP1, XP SP3, Vista) Win installation CDs would start, I kept on receiving the same message on the black screen: Reboot and Select proper Boot device or Insert Boot Media in selected Boot Device.
I checked the CDs at my old home PC and at my office PC and they were all OK, they started normally. So I took Linux Ubuntu 7 Live CD, and it booted with no problems, so I formatted the hard drive (Hitachi, 500gb, SATA2 7200rpm) using gparted: I set 2 partitions, one as FAT32 and the other as NTFS, then rebooted, inserted Win installation CD, but again I got the black screen along with the: Reboot and Select proper Boot device or Insert Boot Media in selected Boot Device.
It's interesting that all bootable CDs start normally (like Hiren's Tools, KillDisc, all Linux distributions I own...) except Win CD. I even brought installation CD from my work PC, and still nothing, the same message...
I called my vendor, but all I got was the line that they sold me a tested and functional machine, and that I should ask an installation expert for help (?!).
What I'm asking is there a reasonable explanation why Win SetUp won't start, is there anything I can do without plugging my old hard drive into my new PC (I can't do the opposite, for my old motherboard has only IDE slots, and my new hard drive is SATA).

Thanks in advance.