Você já tentou set t_Co=256
no seu vimrc para ativar o modo de 256 cores?
Mas isso também depende dos recursos do seu terminal.
Então, se as configurações no vimrc não forem suficientes, sugiro que você dê uma olhada na variável TERM
do terminal que está usando:
echo $TERM
para ver qual é a configuração atual.
O resultado deve ser: xterm-256color
ou screen-256color
.
Para definir o TERM:
export TERM=xterm-256color