Eu acho que você precisa remover a linha
set mouse-utf8 off
Meu ambiente é semelhante ao seu. Eu uso Ubuntu 12.10, Tmux 1.7, Gnome-terminal e Konsole. Eu não tenho esse problema sem essa linha. Eu não encontrei o ajuste de personagem no Gnome-terminal, mas no Konsole é o Utf-8.
Nota lateral: não use o mouse, o teclado é muito mais rápido.