Q: Uninstalled Lion AppStore, Need it back!

I doubt you really deleted it:

Find it in your Applications folder, and drag it back to the Dock.

Hi...

I had accidentally deleted the Lion AppStore

You may have inadvertently "hid" the app... 

Follow the instructions here  >  Mac App Store: Hiding and unhiding purchases

Maybe it is just in the trash-folder, if it is in it, drag it back to the Application Folder and then drag it then back to the Dock.

As John Galt already posted, i dont think you realy deleted it from your MBP:

Then you need to download and install the most recent Lion update. Doing so should restore the MAS.

OS X Lion Update 10.7.3 (Client Combo)

http://support.apple.com/kb/DL1484

Stay away from Clean My Mac if you do not really know how dangerous it can be.

Yes, it is a large file, but it is the only way to get the MAS again.

I used CleanMyMac to remove my apps + their associated files.

Then your problems have just begun. Research how to eradicate it.

Here is one horror story:

Dennis Madsen wrote:

 

I've used CleanMyMac to remove Aperture from MBP today. I think, that this almost destroyed my Mac. It seems that some fonts are missing, since some of the alert messages seems very strange. Further the dock is not appearing and generally it works very slow.

Here is another: https://discussions.apple.com/message/15658273#15658273

Do not install such junk on a Mac.