|Start the computer and put the cd in. Reboot. Make sure the cdrom is the first listed boot device in the bios.|
The cd may be the same used to install your OS the first time but it sees all your updates.....so by booting off the cd rather than your hard drive you wont get that message.
Have you tried doing a repair install yet?