Google API returning Access Not Configured

In my case the needed API was not enabled.

To enable:

1. Go to https://console.developers.google.com
2. Click the menu icon in the top left
3. Click API Manager from the menu
4. Search for your API in the search bar (e.g. YouTube Data API v3) and click on it
5. Once on the subpage for that API, click Enable in the top left

remove all "allowed Ips", then Any IP allowed

I found the solution. Apparently I needed to register my server's IPv6 address, not the IPv4's. Worked without any code changes after adding them.