Das nette Download-Tool youtube-dl muss sich schnell den aktuellen Gegebenheiten von Google und Co. anpassen. Die Variante aus den Paketquellen ist daher nicht zu empfehlen. Glücklicherweise steht das Tool über PIP zur Verfügung:
sudo apt install pip
pip install youtube-dl
Kommt es später wieder zu einem Fehler, aktualisiert folgender Befehl das Programm:
pip install youtube-dl --ugprade