MacBook Pro won't boot. Ideas?
That error means it failed to connect to the network. Is your network perchance WPA or WPA2/WPA mixed with a password? Apparently Internet Recovery doesn't play well with those (another link).

Did that new hard drive have OS X installed or not? If not, it wouldn't be able to boot for obvious reasons. Just to make sure.

Have you tried creating a bootable version of Apple Hardware Test?