I've dug a little and found this:
http://www.pcguide.com/vb/showthread.php?t=69036
The most important thing I took away from it was that it's very much possible (even probable) that the drive has no hardware problem.
The best thing would be if you could prove it by putting it into an USB external enclosure (or another computer), and running tests on it.
One solution there was running chkdisk on it, which seemingly repaired it (but you can't run chkdisk on a harddrive which has no partitions on it, can you?).
Another solution was that in the BIOS, he set the SATA mode from AHCI to ATA.
I had an idea (but it's not supported by any means), that maybe the system is looking for a specific partition (the computer's original hard drive comes with a recovery partition) or partition setup, and when it can't find it, it complains. Do you have the original hard drive around? If I had my hand on it, I would try to "clone" its partitions somehow to the new drive, and try to run the built-in recovery to install the system. Something like this.