Cannot format newly installed HD in MacBook Pro mid 2012 13"
If you are in internet recovery you should be able to format the drive as it downloads a minimal system on a RAM disk (from what I have heard...) and boots from that.

That error needs some more diagnostic info in order to help. Do you still have the old drive you can put back in and boot from? Then an external case to put the new drive in? If so do that and see if you can format it that way. If not report back with some more details.