Para remover pacotes não resolvidos, dê uma olhada here
Aqui está como eu instalei o youtube-to-mp3. Faça o download da sua arquitetura preferida 32bit ou 64bit .
Uma vez baixado, basta pressionar Ctrl + Alt + T no seu teclado para abrir o Terminal. Quando se abre, navegue para onde o arquivo foi baixado, provavelmente a pasta de downloads, e execute o comando abaixo:
sudo dpkg -i <file_name>.deb
Ou você pode usar o Gdebi para instalá-lo.
Isso instalará a versão mais recente (3.6) do youtube-to-mp3