App Store can't verify purchased applications
Short of calling Apple Support (or web chat or twitter @AppleSupport) you could check a few things:


date and time are correct and set automatically
sign out and in to the App store with your Apple ID
delete the app in Launchpad and download it again (make a backup in case the app has been pulled from the store)
make a new user account - delete the app and re-install it from the new user
restart the OS