Я думаю, что вам нужно удалить строку
set mouse-utf8 off
Моя среда похожа на вашу. Я использую Ubuntu 12.10, Tmux 1.7, Gnome-терминал и Konsole. У меня нет этой проблемы без этой строки. Я не нашел настройки символов в Gnome-терминале, но в Konsole это Utf-8.
Примечание: не используйте мышь, клавиатура намного быстрее.