問題を切り分けるために簡単なチェックをしてみるというのはどうだろう。
コマンドラインから以下のように入力してみて「テスト」と表示されたら
Tkinter (Tcl/Tk) は正常だと思う。
$ python2
>>> from Tkinter import *
>>> Label(text='\xe3\x83\x86\xe3\x82\xb9\xe3\x83\x88').pack()