I'm still trying to figure out how you deleted it in the first place. When I try to do that on my 10.7 systems, I get the message "'App Store.app' can't be modified or deleted because it's required by Mac OS X." Did you delete it through Terminal or something?
Also, you backed up the system AFTER you deleted App Store.app off the computer, how would restoring from that same backup help matters? I would just re-run the OS X Lion installer to repair the OS, I do not see any need to do a clean/blank install.