Esses problemas geralmente indicam um valor errado de TERM .
Aparentemente, o valor correto é gnome-256color . Eu não sei porque xterm-256color não funciona também. Esse é o novo padrão (pelo menos no Ubuntu 16.04 LTS, com o Gnome Terminal 3.18.3).