Use a seguinte sequência de comandos:
sudo add-apt-repository ppa:texlive-backports/ppa
sudo apt-get update
sudo apt-get install texlive-full
Isso vai te dar a constelação completa do pacote TeXLive. É mais de 1 Gb de material, mas você nunca se preocupará em perder pacotes novamente. Ambos textlive e texlive-base fornecem apenas um subconjunto de pacotes para a economia de espaço.