One problem that some people are having with the new Mac OS X Lion release is that the downloaded installer appears to be getting corrupted during the download process. After purchasing and downloading the installer, some find that the system will claim that the software cannot be verified after it has been launched.
Multiple users have confirmed that the MD5 checksum for the installer disk image is "b5d3753c62bfb69866e94dca9336a44a," and you can check this on your downloaded installer by running the following command in the Terminal (copy and paste it):
/sbin/md5 "/Applications/Install Mac OS X Lion.app/Contents/SharedSupport/InstallESD.dmg"
Once you've run this command, it may take a few moments to complete, but if the resulting checksum number is different from the one above then you will likely need to download the software again. Unfortunately, some people are finding after downloading the software that the App Store claims it is already installed; but try first deleting the current Lion installer application and then relaunching the store to see if this helps (optionally, try restarting the computer as well).