Desculpe pessoal, eu adicionei alguns ppa extras, então eu os desabilitei na Atualização de Software. Agora estou usando apenas os repositórios originais do Ubuntu. Então eu fiz
sudo apt-get install texlive-lang-european
para instalar o pacote europeu. Agora eu acho que posso usar o norsk (na verdade ainda trabalhando em eiditing um template que usa american-apa e outras coisas).