I had a problem where I had XCode 4.2 beta installed on Snow Leopard, upgraded to Lion, downloaded the free version on the App Store, and kept getting this when I clicked either the already installed XCode.app, or the Install XCode.app.
This is a totally confusing alert by the way
I used this to uninstall XCode and the dev tools:
sudo /Developer/Library/uninstall-devtools --mode=all
and yet the Mac App Store said I had XCode installed (though I had appeared to have successfully uninstalled 'XCode for Snow Leopard'). I couldn't figure it out, and couldn't re-download the Mac App Store version of XCode (4.1 for Lion).
Finally, I searched for the term 'XCode' on my system, and saw the 'Install XCode.app' in a folder named the same, also in my /Applications folder. I noticed that the one outside the folder had a much older date and the version number was 4.02. The one inside the folder (Macintosh HD/Applications/Install XCode/Install XCode.app) had the right version and right modified date. That was the right one.
Hope this helps someone.