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