I figured this one out. The problem is that this particular API is instantiating the YouTubeService without the required Google API key.
If I use the jars provided by the official YouTube API and instantiate the YouTubeService with the Key it works just fine.