The only difference Ive noticed with Lion and the new MBA is that each web page seems to need to reload in that the blue bar always seems to need to go all the way across the page THEN the page loads. Im attributing this to it being a new OS and not the speed of the computer.
To answer the original question, though, no I haven't really noticed a lag with the App store. Then again I don't do much in there.