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).