You need to update youtude-dl on a regular basis because youtube changes things around to prevent downloading videos.
Sometimes the version of youtube-dl is dated from the repos. To update youtube-dl directly from the net, open a terminal and as root, type
Updating usually fixes the downloading issues. It has for me.
Sometimes youtube-dl will throw an error if the format isn't available. To check available videos formats, type
youtube-dl -F youtube_link
This will give you a list of video formats from the best quality to the least quality. To download the video format 18 for example just type
youtube-dl -f18 youtube-link
You can also install a firefox plugin called Downloadhelper. In firefox, click on Tools > Add-ons and enter downloadhelper in the search box.
Downloadhelper can download youtube videos and videos from other sites. Some sites will not work with Downloadhelper just to let you know.