Este PPA deve resolver seu problema, desde que você esteja executando as últimas 12.04.
Abra o Terminal Ctrl-Alt-T
e digite:
sudo apt-add-repository -y ppa:picaso/octave sudo apt-get update sudo apt-get install octave sudo apt-get install liboctave-dev