Another clue: if I execute plot(1:10) in octave (in CLI mode) I get the following errors: http://pastebin.com/aEirBZpk
I also saw the thread http://octave.1599824.n4.nabble.com/ft-render-runtime-errors-td4656976.html which says this might be related to libgl, Freetype or Fontconfig. I made sure I have the packages libfreetype and libfontconfig. I am not sure what package I need for OpenGL, what I have is the package libgl1-mesa-dev, also installed freeglut as I saw somewhere on Ubuntu forums it is needed for OpenGL support.