The gnome-terminal in later versions of Ubuntu already supports 256 colors, however it still reports its term type as "xterm" indicating it supports only 8 colors. This over-conservative report creates small issues for some applications such as "tmux", because "tmux" decides the number of supported colors based on environment variable "TERM".
Most instructions online tell you to add an extra line "export TERM=xterm-256color" in your .bashrc file in order to support 256 colors. However, this extra line sometimes creates problems because environment variable "TERM" should be reported by the terminal instead of the shell. For instance, "tmux" usually sets TERM to be "screen-256color" in order to better support special keys such as "Home" and "End". However, the extra line "export TERM=xterm-256color" would overwrite tmux's terminal type and create annoying issues such as the home key not working. Therefore, what I would suggest is to set the terminal type in the command of your gnome-terminal (Profile Preferences => Title and Command => Run a custom command instead of my shell). For example, if you are using bash, set the command to be "env TERM=xterm-256color /bin/bash".
There are several ways to check whether your terminal colors are set correctly. For example, http://www.frexx.de/xterm-256-notes/ provides you several shell scripts to do that. Vim 7.3 allows you to run "runtime syntax/colortest.vim".
If you would like to know more about environment variable TERM and how the system deals with it, you could take a look at http://wiki.henryhu.net/wiki/TERM (in Chinese though).