Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Just get a new hard drive and put it in...

That's what I did when mine failed with similar symptoms. Everything is fine now and it was pretty cheap.
 
The hardware test is only useful if it finds something, which seems to be rarely. It finding nothing tells you very little about the state of your hardware, unfortunately. Given that the Mac boots successfully on the restore discs strongly suggests a bad hard drive. I'd still run DiskWarrior or TechTool on it if I had it, though.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.