A versão de youtube-dl
nos repositórios 12.04 está desatualizada, atualize-a com o seguinte comando:
sudo youtube-dl --update
Deve funcionar depois disso.
Se você não tem privilégios de root, defina um arquivo de saída como solução alternativa:
youtube-dl -o ~/Videos http://www.youtube.com/watch?v=P0YiWsAM0O8