A cópia de youtube-dl nos Repositórios do Ubuntu é muitas vezes bastante antiga e o Youtube frequentemente altera a forma como serve ficheiros que tornam versões mais antigas de youtube-dl ineficazes. Use o seguinte para obter uma cópia moderna:
sudo apt-get remove -y youtube-dl
sudo wget https://yt-dl.org/latest/youtube-dl -O /usr/local/bin/youtube-dl
sudo chmod a+x /usr/local/bin/youtube-dl
hash -r
Você deve descobrir que seu erro não será mais exibido. Rotineiramente atualize sua instalação (toda semana ou mais) executando:
sudo youtube-dl --update
Na verdade, será obrigatório que você atualize / atualize desta forma, pois youtube-dl não será um pacote padrão do repositório Ubuntu.
Referência: