I know this post is old but I was having the same problem with my 2009 MBP and thought others may be too. Orignal HD quit and I couldn't boot under any mode. Oddly enough when I disconnected the HD and plugged it back in, it fully booted before crashing, then back to the original failure to boot every time after. I bought and installed a new SSD but wasn't able to format/erase due to the same "cannot allocate memory" error using Disk Utility or Terminal. After playing with the SATA cable a bit just to make sure it had good connections I was able to format the drive and install 10.6 with no problems. I think that would explain why unplugging the original HD and plugging it back in allowed it to boot once. It's been a day since I installed OSX on the new SSD and I haven't had any problems. I'm going to replace the SATA cable just to be sure, but I think this may be the problem for others with older MBPs who are trying install a new drive.
If you're having this problem trying formatting the new HD via a USB/SATA cable (instead of in your macs HD bay) before you return the drive or give up. Worst case you'll rule out the SATA connection, but this worked for me.