The tmux FAQ ( http://tmux.cvs.sourceforge.net/viewvc/tmux/tmux/FAQ ) explicitly advises against setting TERM to anything other than screen or screen-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.