Tente
sudo apt-get purge texlive-*
sudo apt-get autoremove
sudo apt-get autoclean
Eu instalei o texlive 2009 no meu sistema por acidente, e usei todas as maneiras que eu sei para removê-lo. Não funcionou ...
sudo apt-get remove texlive
Reading package lists... Done
Building dependency tree
Reading state information... Done
Package texlive is not installed, so not removed
0 upgraded, 0 newly installed, 0 to remove and 0 not upgraded.
mas se digitar tex no terminal ...
tex
This is TeX, Version 3.1415926 (TeX Live 2009/Debian)
Tente
sudo apt-get purge texlive-*
sudo apt-get autoremove
sudo apt-get autoclean