problema resolvido:
embora não tenha funcionado quando postei a pergunta original, tentei novamente e excluí o 'youtube-to-mp3' com
sudo apt-get purge youtube-to-mp3
e funcionou. O pacote sumiu, mas o ícone [na verdade, o ícone desapareceu e apenas o nome] permanece no menu da área de trabalho. A instalação / remoção de outros aplicativos e pacotes está funcionando bem e sem erros novamente.
Não tenho certeza, mas acho que quando tentei excluir o pacote antes de usar
sudo apt-get remove
em vez de purge
. Então talvez essa fosse a solução.