Back up your data first and make sure you have all drivers necessary (graphics, dvd, sound etc). If not, get them all before reformatting.

Have you tried shutting down with the restore CD in the laptop, and starting up so it boots from CD?

If that don't work, take out the hard drive and put into an external 2.5" USB2 caddy and plug into another computer.

Format it, then replace the hard drive. Then install from the recovery CD.

If you have a spare 2.5" hard drive, try a reformat on that to ensure everything works first.