Digite o seguinte no terminal:
sudo dpkg --clear-avail
Você precisa editar o arquivo e remover manualmente os caracteres ofensivos. Faça um backup do arquivo existente.
sudo cp /var/lib/dpkg/status /var/lib/dpkg/status.bad
gksudo gedit /var/lib/dpkg/status
Vá para a linha 60773 , 60774 e 64482 . O problema parece ser que o sublinhado se tornou, em algum momento, um caractere ilegal nos nomes dos pacotes Debian. Edite as linhas ofensivas, altere todos os sublinhados para tildes ( ~ ) para resolver seu problema.