This one always troubles me each time I need to re-install Ubuntu. The solution?

 sudo apt-get install ncurses-term

Done.