Finalmente, encontrei um link e isso resolveu o problema.
Re: Erro ao compilar a oitava 4.0 no ubuntu 14.04
Precisamos excluir os arquivos antigos relacionados à octave antes de reinstalá-los em uma versão atualizada. E então peça ao Ubuntu para continuar com a instalação anterior.
sudo rm -rf /usr/local/{bin,include,lib,libexec,share}/octave*
sudo rm -f /usr/local/bin/mkoctfile*
sudo apt-get -f install