Try this instead because youtube-dl no longer seems to work as of September 22, 2024

sudo snap install video-downloader

Check your version with: youtube-dl --version

Try ppa:nilarimogard/webupd8. I do get upgrades every couple of days and I think, according to the message You get, that it should solve/answer Your question. If You did an upgrade from 13.04 to 13.10 You might have forgot (I guess) to update sources-list.d folder, for example, if You used WebUpd8 before.

$ sudo apt-add-repository ppa:nilarimogard/webupd8
$ sudo apt-get update
$ sudo apt-get install youtube-dl

Usage:

$ youtube-dl -f mp4 --output "yourfilename.%(ext)s" https://youtu.be/your-link-here
$ youtube-dl --extract-audio --audio-format mp3 --audio-quality 256 --output "yourfilename.%(ext)s" https://youtu.be/your-link-here

If you are getting a warning about avconv being out of date.

Refer: https://askubuntu.com/questions/563245/avconv-warning-while-downloading-youtube-video

before

$ avconv |& grep \ version | awk '{print $3}'
9.18-6:9.18-0ubuntu0.14.04.1,

$ sudo add-apt-repository ppa:heyarje/libav-11 && sudo apt-get update
$ sudo apt-get install libav-tools

after

$ avconv |& grep \ version | awk '{print $3}'

Issue now requires the enter key to be hit to finish the download