Surely you downloaded Lion originally. If you can't gain access to the App Store and you have access to another computer, log into the Apple Store and redownload Lion. You can make a bootable Lion Installation Flash disk.
You should actually be able to access the App Store from 10.6.8. Instead of doing any restoring of old information, you should have just reinstalled the old OS, then updated to 10.6.8. Then you should be able to access the App Store and download Lion again. After installing Lion, then restore your user data.
Thank you. As I still have my Time Machine back up on an external drive, can I go ahead and erase my hard drive again and start all over again and go through the steps in the second part of your response, install the original, update it to 10.6.8, go to the App Store, download Lion again or pay for the upgrade to Mountain Lion and after that restore my user data or is it too late?
Yes, you can do that.
If you have a full TM Lion backup, why go through the steps to reinstall 10.6.8? Assuming you have Lion on the TM backup, you can boot from from the recovery drive that should be on the TM drive.
Restart and hold the option key down. Choose from the list of startup drives. You should have one called Mac OSX which should be the TM recovery drive (not 100% sure on the name). Once booted from it, just follow the restore entire system from the TM backup and choose a date when you new it was working properly. Your whole OS and files should be restored. Once completed, follow the steps to restart and you should be back up and running.
Also, you can go back to the App Store after and redownload Lion again and make a Recovery Flash Drive if you wish.
Check out this link here:
In addition to those steps, check the format of the new drive and be sure it is Mac OS Extended Journaled. If it isn't, reformat it before restoring.
Also, since you have an older computer, the recovery drive is not built in the hardware and the new drive won't have the recovery partition on it. So, you will have to follow the steps to boot holding the option key down and using the recovery partition on the TM drive as I have stated earlier.