Issue is solved.
As I said, switching out the hard drive and performing a recovery did not work.
I took it back, and they performed a clean Windows7 install... which worked.
I wasn't particularly happy, since I lost a few programs, like Media center, and roxio, which came pre-installed, since they did a bare bones install. I also told them that I was concerned about buying the hard drive, since it didn't solve the issue. So they said they'd take it back, if I could get the old one working.
So... I created a startup repair disc from the new Windows 7 install. Then I put the old hard drive in and booted. Windows 7 actually started this time, but hung up before the desktop appeared. I then booted to safe mode, and a blank desktop appeared. So I booted from the repair disc, and it didn't find any errors.
So I recovered the hard drive again... and booted to the original error. I then booted again from the startup repair disc, which this time found a boot file error, and fixed it.
Windows 7 then loaded! I performed updates and successfully restarted. I then replaced the trial programs with my permanent ones, and updated again. During this period, the computer restarted about a half dozen times. All successfully. So far, I have restarted the computer about 20 times, all with no issues.
So issue seems resolved. I just needed a startup repair disc, which I stupidly neglected to make when I got the computer, thinking the recovery discs would be enough. I am a little confused about why there is such an error on the recovery discs, since making them was the first thing I did when the laptop came out of the box.
So, just getting ready to return the replacement hard drive and get my money back.
Hope this helps those with a similar issue.