This error occurs in two cases:
1. "URL Shortener API" is turned off at Google API console of your project API options. To fix this just go to API options of your project and enable the "URL Shortener API". After that, in some cases, you will have to create a new API key or recreate the current one.
2. The "Referers" field at public API key options is not empty. To fix this you need to clear the "Referers" field and recreate API key.