Access Not Configured Android Google API Key

I've finally solved this. I deleted my project and created a new project in the old Cloud Console. I then activated all the APIs I need to use and then went into API Access and there was a key already there. It should say "Key for browser apps (with referers)" and I just used that key, and it works.

A bit mind confusing is that for the YouTube Data API you need to use the browser-key, but for the YouTube Player API (for Android) you need the Android-key.

Using the Android key for the YouTube Data API will not work and result in the error you received.