Can't open disk utility at startup, can't format new hard drive

21st,

do you have an Early 2011 model, or a Late 2011 model? If you have an Early 2011 model, did it originally come with two grey installation DVDs in the box?

21st,

not all Early 2011 models came with DVDs, and no Late 2011 models came with DVDs — that’s why I’d asked which model you have. Your internal disk needs to have a recovery partition installed on it to be able to use ⌘R to boot into Recovery mode; your new unformatted disk will not have a recovery partition on it, so ⌘R will be unavailable. If your MacBook Pro originally came from the factory with Lion installed, then you should be able to use OS X Internet Recovery to install Lion onto your new disk when installed internally by downloading it from Apple’s servers. If you have an Early 2011 model and it originally came with Snow Leopard installed, then you’ll need to purchase a replacement pair of grey installation DVDs for it to be able to format your new disk without having access to a bootable disk.

That is a Great question.

This computer may have been issued with firmware that does NOT contain Internet Recovery, BUT it is upgradeable to new firmware that DOES contain Internet recovery. So, it depends.

Computers that can be upgraded to use OS X Internet Recovery

I have used Internet Recovery on a new, bare drive when I purchased my Late 2011 MacBook Pro. I purchased the system and a new (upgraded) HDD for it. Before ever booting the system, I replaced the original HDD with the new one, then used Internet Recovery to partition my drive and re-install a clean Lion installation.

As has already been said, if your system originally came with the install DVD's, then you should use those. If it didn't then you should be able to use Internet Recovery for that.

You can use an external USB disk/flash drive which has Recovery (or a full OS - requires a 16GB disk space on a USB flash or a JHFS+ partition with the OSX) on it. Boot from that recovery USB drive. if Internet Recovery worked once, the MBP is already capable of repeating it. It requires an Ethernet or WiFi connection. If neither is available, or is spotty, Internet Recovery will not work. Can you try Internet recovery via Ethernet cable, if all your previous attempts have been via WiFi?

If the drive is not recognized when plugged into the internal SATA bus, either a cable is not plugged in properly (the replacement drive never showed up successfully as per the OP even once, or the drive is DoA). It should be tested externally. Pulling the drive out and putting it back is fairly easy in the 2011/2012 MBPs. The cable could have been damaged during the replacement. The non-drive end of SATA/IR Sensor cable on the main logic board could be loose or damaged.

If you have a external cable SATA-to-USB or SATA-to-FW (very unlikely), format the new drive using a different PC/MAC to make sure it is not DoA. What brand/model is this new drive? Is it an SSD? It may require a FW upgrade.

If there is a second MAC available, a Target Disk Mode boot (press T while powering up the mac with the new drive) may allow the second working mac to format the new drive via Disk Utility.