Aparecem em várias documentações na rede que o Texlive 2012 não assume instalações anteriores de pacotes do TexLive para o Ubuntu. Assim, é imperativo remover completamente o TexLive de um sistema, antes de instalar uma nova distribuição do TexLive.
As instruções para remover / expurgar texlive são dadas nesta página . Apesar disso, minha nova instalação não estava funcionando. Por isso fiz o seguinte, depois de seguir completamente as instruções no link acima:
sudo apt-get purge tex-common
sudo apt-get install tex-common
e depois disso, é possível instalar novamente o TexLive a partir da distribuição Ubuntu 13.04.