Disconnect the TimeMachine drive.
Connect the external USB enclosure with the old hard drive inside, see if you can hold the option key and boot from it. If not, then use another Lion Mac.
Download this software here:
Get a 1GB+ USB thumb drive, format it GUID OS X Extended in Disk Utility > Partition Tab
Run the Lion Disk Assistant software to copy the Lion Recovery Partition to the USB thumb drive.
Take that to the "new hard drive Mac" and option boot off of the USB, you will need a strong fast, reliable internet connection to install Lion.
Hold command r keys to boot into Lion Recovery Partition.
Big thank's for that help. But I'm still confused why I could not erase the old internal hard drive when it was in the machine. It makes me thinking that maybe the hard drive was not the problem. But what else could it be?
(I have Lion on an external drive so I used that to boot and ried o repair/erase from)