When you log into Gmail from an IP address that is in a different location than your usual one, Gmail flags the login as suspicious and blocks the attempt. To clear this, simply login to your account at https://mail.google.com (or the secondary email that you associated with your Gmail account) and look for a suspicious login email. Open this email and look for the part that says: "If this was you, and you are having trouble accessing your account, complete the troubleshooting steps listed at http://support.google.com/mail?p=client_login". Click the link in the email, then go to steps 3 and 4 on the next page.
If you're still having problems after this, you can visit http://www.google.com/accounts/DisplayUnlockCaptcha on Google's site, and sign in with your Gmail username and password. If necessary, enter the letters in the distorted picture. Afterward, click Continue. Skip all the other steps, only do steps 3 and 4.
You will likely have to do this a few times for each VPN server you use until Gmail remembers a selection of IP addresses that you use often.