Você instalou via apt-get? Parece que esta versão está desatualizada. Isso estava acontecendo comigo:
$ sudo youtube-dl -U
It looks like you installed youtube-dl with a package manager, pip, setup.py or a tarball. Please use that to update.
Você pode instalá-lo a partir de fontes oficiais: link
Usando o curl :
sudo curl -L https://yt-dl.org/downloads/latest/youtube-dl -o /usr/local/bin/youtube-dl
sudo chmod a+rx /usr/local/bin/youtube-dl
Se você não tiver o curl, você pode usar wget :
sudo wget https://yt-dl.org/downloads/latest/youtube-dl -O /usr/local/bin/youtube-dl
sudo chmod a+rx /usr/local/bin/youtube-dl
Você também pode usar pip :
sudo pip install --upgrade youtube_dl
Você também pode usar o Homebrew :
brew install youtube-dl