https://rg3.github.io/youtube-dl/download.html
Der Anleitung folgen.
Ganz einfach. 
apt-get install curl
curl https://yt-dl.org/downloads/2015.11.27.1/youtube-dl -o /usr/local/bin/youtube-dl
chmod a+rx /usr/local/bin/youtube-dlKleiner Check:
wget https://yt-dl.org/downloads/2015.11.27.1/youtube-dl.sig -O youtube-dl.sig
gpg --verify youtube-dl.sig /usr/local/bin/youtube-dl
rm youtube-dl.sigGruß! 
Ist auch irgendwie die einzige Anleitung, die bei mir funktioniert..
so... ich hab das jetzt mal gemacht... die Fehlermeldung kommt leider immernoch.
Quelle: Meine virtuelle Maschine
Keine Ahnung was du falsch machst.
Machst scheinbar vielen nicht richtig.
Hast du überhaupt Python installiert?
Falls nicht -> installieren und Informationen über dein System.
Gruß.
YouTube sperrt einige IPv6 Blöcke von größeren Hostern, unter anderem auch OVH und online.net. Ich würde mal darauf tippen das du auch davon betroffen bist.
Du kannst mal versuchen youtube-dl mit --force-ipv4 Parameter zu starten. Wenn das auch nicht hilft versuchs mal via Proxy.
Eventuell Informationen über das System? So können wir auch nicht viel mehr machen außer Hoffen. 
