You need a terminal application that supports 256 colors, and a TERM
environment variable that also points to a 256-color terminfo. The number of colors available to your terminal has nothing to do with the rest of your setup :)
Try in your console:
export TERM=xterm-256color
vim
It might not work with your terminal program, but for recent versions of xterm, it does.
Terminals vary a lot in their capabilities; some terminals are very dumb (think of a keyboard with a line printer); some are very narrow, some are paginated, some support underlining, some have colours, some have unusual keyboard mappings, and so on. To support all of these, there needs to be a database of capabilities for each terminal, so that applications know what they can and cannot do; that's the point of terminfo and of TERM. By declaring TERM=xterm-256color
you're indicating to applications that your terminal supports the xterm capabilities including 256 colors. You can have a look in your /usr/share/terminfo/ directory to see the incredible number of terminals that are supported by your box, and man terminfo
will show you the sheer number of configurable options for terminals.