A remoção de pacotes é feita por um nome de pacote, não por nome de arquivo.
Você pode removê-lo por
sudo dpkg --purge youtube-dl
Este comando também removerá arquivos de configuração desse pacote.
Apenas para remover o pacote e deixar as configurações, execute
sudo dpkg -r youtube-dl
Se você apagou alguns arquivos do pacote manualmente, você pode receber uma mensagem de erro
package is in a very bad inconsistent state; you should reinstall it before attempting a removal Errors were encountered while processing: youtube-dl
Nesse caso, reinstale-o novamente e remova
sudo dpkg -i youtube-dl_2015.06.04.1-1~webupd8~trusty0_all.deb
sudo dpkg -r youtube-dl
E no futuro nunca exclua nenhum arquivo instalado por pacotes deb!
Isso pode quebrar todo o sistema