На официальном сайте есть бинарник.
http://rg3.github.io/youtube-dl/ Скачиваете распаковываете в удобное место, и запускаете. Ничего устанавливать мимо пакетного менеджера не надо.
./youtube-dl ссылка
проблемы бывали в версии из основного репозитория. Это тот тип софта, работа которого зависит от "дяди" так что не самая новая версия в данном случае не хорошо. А вот предложенный PPA я бы не стал использовать, куча всего там... А вот что там у вас на сервере не работало, не знаю, разницы не может быть в данном случае между сервером и десктопом.