Seu problema é quase certamente porque você está executando uma versão mais antiga de youtube-dl
.
Você deve desinstalar a versão apt com
apt-get purge youtube-dl
e, em seguida, instale-o com pip.
pip3 install youtube-dl
Se você não tem pip3, você pode instalá-lo com
apt-get install python3-pip
ou veja isto para mais ajuda sobre isso.
O pacote youtube-dl
no repositório do apt para jessie (e talvez até mesmo fiel) não foi atualizado em quase um ano.