`.. hp recovery disc which was created when the computer was first set up.`
Is this a disk that was supplied by HP or one that you made yourself? If the CD isn`t burned as bootable it wont work.
HP were slated recently (if my memory is right) for not supplying recovery media with their laptops, so if you contact them they should provide you with a recovery disk free of charge.
For the future I suggest you get a copy of Acronis True Image, or similar, and keep a full, validated backup on an external drive. That way if you do have a hard drive failure you can simply boot from the Acronis disk and reinstate the drive from the backup.