Como outras perguntas sugeriram, acabei de instalar todos os pacotes texlive no meu sistema e isso não resolveu o problema do Lyx não encontrar classes.
Isso foi corrigido desde 12.04 ou ainda é um problema?
Isso pode estar relacionado ao diretório texlive estar fora do sistema texmf original?
Eu resolvi isso usando este post.
% bl0ck_qu0te%Você precisa excluir o diretório home .lyx de fora do lyx e, em seguida, executar novamente o lyx. Ele reconfigura e, em seguida, os arquivos de classe .cls são encontrados. Deve ser um problema de cache.