I had the same problem on a MacBook Air that ships with Lion
This is how you fix it
0. Close Every App (Safari, iTunes, AppStore, etc)
1. Launch Finder
2. Press CMD+SHIFT+G (or click on Go then Go To Folder)
3. Type the following /var/folders
4. Open up Console (Spotlight Console and launch it)
5. Open The AppStore
6. Try to buy something free and you will see this message "The product distribution file could not be verified. It may be damaged or was not signed."
7. Switch to Console and look at the error message
8/31/11 6:50:37.121 PM App Store: FRPurchaseManager: Preflight operation for 415571499 failed with error: Error Domain=com.apple.appstore Code=0 "The product distribution file could not be verified. It may be damaged or was not signed." UserInfo=0x7f9b2464aa00 {NSLocalizedFailureReason=Cannot create PKProduct from "file://localhost/var/folders/3p/sflvgxwj3hs4kdkjpgb30r4c0000gn/C/com.apple.app store/415571499/preflight.pfpkg" Error Domain=NSURLErrorDomain Code=-1100 "The requested URL was not found on this server." UserInfo=0x7f9b2464ac00 {NSUnderlyingError=0x7f9b24648230 "The requested URL was not found on this server.", NSErrorFailingURLStringKey=file:///var/folders/3p/sflvgxwj3hs4kdkjpgb30r4c0000gn/C/com.apple.appstore/41557 1499/preflight.pfpkg/index.sproduct, NSErrorFailingURLKey=file:///var/folders/3p/sflvgxwj3hs4kdkjpgb30r4c0000gn/C/com.apple.appstore/41557 1499/preflight.pfpkg/index.sproduct, NSLocalizedDescription=The requested URL was not found on this server.}, NSLocalizedDescription=The product distribution file could not be verified. It may be damaged or was not signed., NSUnderlyingError=0x7f9b2464ac40 "The requested URL was not found on this server."}
In my case the problem was some file in the /var/folders/3p
5. Quit AppStore
6. I deleted the entire 3p folder (it gets recreated when you launch AppStore). If you really want to be safe, create a copy of that folder.
You don't need to restart. Just Launch AppStore and it works!