Make sure that your bios is set up to look for the CD as a boot device. When the computer boots, it usually says "for setup, hit F2" or the like. Hit F2 and go into the setup and tell the computer to look for the CD first, Floppy second then hard drive third.
Put the recover CD back in, shut it down and start it up again and see what happens.
If it does not boot off of the CD I would wonder if your bios motherboard battery has gone dead and lost its settings. To check it, look in your laptops book, and find the bios battery. Find the size and get a new one. Take it out and put the new one in and go back to the setup as all your data may be lost on the boot up sequence.