If you're getting that message, then it's not booting off the CD. It's looking for the specified boot device, and not finding it.
You can try hitting the Enter key a few times, and see if it's just slow in recognizing the disc. Other than that, my best suggestion, would be to try a different CD drive.
Is it a burned CD? Does it look scratched or smudged? If yes, try cleaning it with a soft cloth, and a few drops of water. That can help the drive read the disc.