This error occurs in two cases:
1. Your API key is outdated. Go to Google API console, create a new public API key there and paste it to the "API key for your goo.gl account" field on the plugin's settings page.
2. Your API key is newly created. In this case, just wait a few minutes.