Para remover completamente o youtube-dl, já que ele já foi instalado pelo comando que você emitiu:
sudo apt-get remove --purge youtube-dl*
sudo apt- get autoremove
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following NEW packages will be installed:
youtube-dl
0 upgraded, 1 newly installed, 0 to remove and 3 not upgraded.
Need to get 0 B/589 kB of archives.
After this operation, 2,960 kB of additional disk space will be used.
Selecting previously unselected package youtube-dl.
(Reading database ... 177811 files and directories currently installed.)
Preparing to unpack .../youtube-dl_2015.11.02-1~webupd8~trusty1_all.deb ...
Unpacking youtube-dl (2015.11.02-1~webupd8~trusty1) ...
Processing triggers for man-db (2.6.7.1-1ubuntu1) ...
Setting up youtube-dl (2015.11.02-1~webupd8~trusty1) ...
Para remover completamente o youtube-dl, já que ele já foi instalado pelo comando que você emitiu:
sudo apt-get remove --purge youtube-dl*
sudo apt- get autoremove