Verifique seus scripts de inicialização do shell. Minha aposta seria que TERM está sendo sobregravado lá. O tmux deve configurá-lo antes de iniciar o seu shell, mas não tem como impedir que o seu shell o redefina.
Tente executar tmux new-session 'bash --norc'
(ou desative os scripts de inicialização no shell que estiver usando) e veja se TERM está definido como screen-256color
. Se estiver, isso confirmaria que TERM é sobrescrito por um dos seus scripts de inicialização.