I had the exact same problem today. I got it to work finally, and I think the issue was that my Lion cloned disk was still mounted, so the app store was seeing the apps "installed" on the secondary drive. When I unmounted the backup drive, I was able to install all but one app - I did a search and found a non-appstore version of an app that was in a "installed apps" folder on my desktop - it wasn't really installed, and had never been run on this install, but the app store apparently just went by the apps file name.
I hope that helps
Thanks for the reply. Not sure if this was the issue or not as I seemed to have found another 'workaround'.
Basically I downloaded a free app that wasn't installed via the app store and also restored an app that the app store was saying was already installed. I then ran them both and then immediately removed them using AppDelete.
Rebooted and relaunched App Store and all is now good.
Thanks for the reply. Maybe both our 'solutins' will help others.