One reason might be incorrect date and time setting on the Android device. The license verification mechanism depends on the correct time being set on a device.

Another reason might be that some VPNs do not allow the Market app communicate with Google servers.
Workaround in this case is to try to connect when you are not on VPN, the connection will fail, but the license will be verified and cached for about a week and you will be able to connect over VPN. Sorry for the inconvenience.

The application is relying on the Google Android Market License Verification service to make sure it is licensed for use on the device. The licensing status is obtained through the Android Market application and cached for the next 24 hours. There has to be an Internet connection (over WiFi or cellular data network) when the application runs for the first time, so that the licensing status can be initially verified. After the licensing status is initially verified, the application can be used for one week without Internet connection. After one week the Internet connection will be required to verify the licensing status.