The Tmux FAQ explicitly advises against setting TERM to anything other than screen or screen-256color or tmux or tmux-256color in your shell init file, so don't do it!
Here's what I use:
~$ which tmux
tmux: aliased to TERM=xterm-256color tmux
and in in my .tmux.conf:
set -g default-terminal "screen-256color"
Aliasing tmux to "tmux -2" should also do the trick.
And don't forget to restart your tmux server: (see @mast3r answer)
tmux kill-server && tmux
