You can always boot a disk even with that Recovery Failed error message. Just tap the ESC or F9 one-time BIOS Boot Menu key at boot and trigger the CD/DVD drive. If you don't get a prompt to Press Any Key to BOot Disk then the disk is not burned correctly.
So boot into Windows 7 DVD or Repair CD command line to run Diskpart, free Partition Wizard bootable CD, or DBAN CD to wipe the HD to see if Recovery Disks will then boot and run to completion.
Other options besides ordering your Recovery Disks from HP are to install the free Win8 Consumer Preview which is quite good although the button-like start screen takes some getting used to - it's just a Start menu with clickable icons which actually starts with Windows. We even have a sister site EightForums.com which will get you all set up and running great. You can participate as we did with Windows 7 beta and earn low cost or free copies as you go from MS.
You can also install a Linux distro which is also free.