1. Ставим urxvt

    sudo aptitude install rxvt-unicode-256color
    
  2. Если терминал ругается при запуске (setterm: ***: unknown terminal type), то делаем следующее:

    echo 'URxvt.termName: rxvt-unicode' >> ~/.Xresources
    xrdb -merge ~/.Xresources
    

    И перезапускаем терминал.

  3. В .vimrc добавляем:

    set t_Co=256
    

    и радуемся полученному результату