O Youtube atualiza seu sistema de segurança anti-downloads. Você deve manter seu youtube-dl
atualizado. A versão que o Ubuntu 12.04 Prec instala por padrão é 2012.02.27 (dois anos).
Você pode se inscrever no PPA WebUpd8 para obter novos lançamentos quando eles estiverem fora (isso é uma vez ou duas vezes por semana):
sudo add-apt-repository ppa:nilarimogard/webupd8 -y
sudo apt-get update
sudo apt-get dist-upgrade
Você também encontrará o pacote .deb da versão mais recente do youtube-dl nesse PPA ( aqui e procure por youtube-dl). Instale-o com uma ferramenta GUI como gdebi
ou Ubuntu Software Center, ou com estas linhas de comando:
cd directory/where/you/downloaded/the/package
dpkg -i youtube-dl*
sudo apt-get install -f