Searching around, I found that it might be a problem with Tmux detecting the correct terminal mode, so I placed this in my .tmux.conf:
set -g default-terminal "screen-256color"
Together with alias tmux="tmux -2" it makes some colorschemes work (badwolf for example), but not all of them (doesn't work for solarized, vividchalk and base16 for example). Since I wanted at least solarized, I installed it to gnome-terminal and to Vim. Colors show properly out of Tmux, but not in Tmux. I also set t_Co=256 (in Vim) but without success.
According to Tmux faq, there is nothing wrong with my configuration, but yet I can't get it to display properly. Any idea?
Update
To give a better understanding of the problem, below are some images.
First, Gvim (left) and Vim (right, in gnome-terminal):

Second, Vim (left, in gnome-terminal), Vim with tmux (right, also in gnome-terminal):

Credits: the code is from Princeton Algorithms course (authors: Robert Sedgewick and Kevin Wayne).