The YouTube addon for Kodi uses the YouTube API. The addon uses keys to authorize with the API. YouTube can blacklist a key for abuse of the API. Since the Kodi addon is too popular, it's being blocked.
Solution (one of several):
Go to the Google Developer Console
Create a project, open the API manager, select YouTube Data API, click Enable
Create an OAuth ID of type "Other", save the resulting JSON file.
Open the JSON file in a text editor and make a note of the strings client_ID and client_secret.
Create an API Key (type "Browser"), save key.
Log out of the YouTube addon in Kodi, close Kodi.
Open this file in notepad or another text editor
In the sections 'youtube-for-kodi-quota', 'youtube-for-kodi-fallback' and 'youtube-for-kodi-15' (replace with your version if you're not running Isengard) replace key, id and secret with the data you generated above.
Restart Kodi, follow the login procedure for the YouTube addon. You're now using your own personal credentials to access the API and therefore are unlikely to be blacklisted for spamming it.
Source: This thread on the Kodi support forum. Feel free to read all (as of writing) 208 pages of this thread for more details. I wrote this summary so that other might more easily find a solution to this problem that appears to resurface every few months.