My nephews computer has the same fault. We just discovered that if you leave the XP CD in the drive, boot as normal and do not press any key when computer asks to "press any key to boot from CD" - do nothing and the computer will start normally. We tried this on four boot-ups and works everytime. Leave the CD out the drive and the dreaded message appears.
Make sure that you set your Boot sequence in BIOS to 1. CD Rom 2. HDD 1