Tente remover o pacote completo (texlive-full). Pode haver alguns resíduos de dependências. Boa sorte.
sudo apt-get purge --autoremove texlive-full
Isso pode ajudar a corrigir os pacotes corrompidos:
sudo apt-get install -f
sudo apt-get update
sudo apt-get upgrade
sudo dpkg --configure -a
Algo a considerar se o acima não funcionou:
sudo apt-get purge texlive*
sudo rm -rf /usr/local/texlive/* and rm -rf ~/.texlive*
sudo rm -rf /usr/local/share/texmf
sudo rm -rf /var/lib/texmf
sudo rm -rf /etc/texmf
sudo apt-get remove tex-common --purge
rm -rf ~/.texlive
find -L /usr/local/bin/ -lname /usr/local/texlive/*/bin/* | xargs rm