Installing OSX on brand new hard drive

I have installed a brand new solid state hard drive in my macbook pro 13" mid 2009.

I replaced the old hard drive because it was failing.

Now that I have the new hard drive installed I am struggling to get OS X installed onto the new hard drive. I have ruled out using a USB enclosure on the old hard drive because it was failing.

I do have the original OSX snow leopard start up disk. I have tried using this to install OSX onto the new HDD but it would not work.

I think it might be because the new HDD is unformatted?

I have also been into disk utility to try to resolve this but this does not work.

I have tried partitioning the new HDD but I get an error message "Partition failed .... POSIX reports: The operation cannot be completed. Cannot allocate memory".

I have also tried the restore function in Disk Utility to restore the disk using my time machine backup disk, but I get the error "Could not erase target - Operation not permitted"

I have also tried to restore the HDD from a time machine backup, but when I try to select a Destination it says the "disk does not have enough space to restore your system"

Any suggestions on how to solve this would be much appreciated!