Se você atualizou algum pacote desde que instalou o sistema operacional, isso pode causar problemas ao tentar instalar qualquer coisa que dependa desse pacote.
A primeira coisa a tentar é apt-get install -f octave
. Isso fará com que o apt tente consertar o problema.
Se isso não funcionar, tentarei fazer o downgrade de todas as dependências que estiverem falhando na versão fornecida com o sistema operacional. (Isso funcionou para mim no passado).
Para fazer isso, você pode usar o Gerenciador de Pacotes Synaptic. Basta usar o pacote > Force Version .. item de menu ou pressione Ctrl + E e, em seguida, selecione a versão marcada com o nome do código da versão (por exemplo, "fiel"). Isso não deve quebrar nada e, afinal, você sempre pode atualizar o pacote novamente.
Como alternativa, você pode tentar usar aptitude
. Ele tentará consertar o problema para você. (Eu nunca usei isso sozinho, mas vale a pena tentar.)