2 etapas:
1) defina TERM para algo diferente de "burro" em .bashrc. O xterm deve ficar bem, já que você está no Ubuntu.
2) Em .vimrc, adicione set t_Co = 256. Isso diz ao vim que você está em um terminal de 256 cores.
Isso deve resolver seus problemas.