Thoughts....
1. It probably gave you an error with the new HD in the old computer because I'm guessing the new computer is 64-bit and maybe the old one is not? So the disc isn't going to work in that computer, processor can't do it.
2. I would unplug everything, make sure all the contacts look clean (blow dust away) and plug back in.
3. When you try to boot the computer to the new hard drive, what is the error? It's going to say something because the drive is not formatted, but hopefully it will at least acknowledge that a drive is installed.
4. Likewise, if your BIOS can run diagnostics on a hard drive (like what you did when the original went bad), try that with the new drive just to make sure it recognizes the drive.
There's a difference between the drive itself failing and some sort of connection failing and sometimes that's hard to determine without starting to replace parts and see...
5. Perhaps the recovery disc can't work with an unformatted drive? Do you have any other recovery/diagnostic bootable discs or even a Windows XP disc? Like something you can boot off of, get to a command prompt, and have it format the new hard drive before reinstalling the OS from the HP disc.