(eu tive o mesmo problema) Isso funcionou para mim no final.
No terminal, instale
sudo apt-get build-dep octave
No synaptic, instale
libqt4-opengl-dev
Então, baixe octave-4.0.0.tar.gz de ftp://ftp.gnu.org/gnu/octave/
descompacte octave-4.0.0.tar.gz para casa.
cd octave-4.0.0
./configure
make
sudo make install
Isso funcionou em todas as máquinas que eu tentei no meu laboratório.