Судоку не работает, вероятная sys.path ошибка

Как заголовок предполагает, игра судоку по умолчанию больше не работает. Я раньше использовал его вполне часто однако, после повреждения, когда я пытался выполнить его снова, это не открывается.

Если я ищу Судоку на тире и нажимаю на него, команда регистрируется, но ничего не происходит.

Я нахожусь на 12,04. Как это может быть зафиксировано?

Править

После попытки выполнить его в терминале как судоку гнома или судоку гнома-v, я получаю следующую ошибку -

Traceback (most recent call last):
      File "/usr/games/gnome-sudoku", line 21, in <module>
        from gnome_sudoku.gnome_sudoku import start_game
    ImportError: No module named gnome_sudoku.gnome_sudoku

Редактирование № 2

Мусорное ведро вставки связывается для -

1) найдите gnome_sudoku

http://paste.ubuntu.com/5864729/

2) Python-c "импортирует sys; печать sys.path"

http://paste.ubuntu.com/5864604/

3) grep-n ""/usr/games/gnome-sudoku

http://paste.ubuntu.com/5864607/

Редактирование № 3

Как lgarzo предложенный, /usr/lib/python2.7/dist-packages может отсутствовать в моем sys.path, и вывод для python -c 'import os; print os.environ["PYTHONPATH"]'

Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/local/lib/python2.7/UserDict.py", line 23, in __getitem__
    raise KeyError(key)
KeyError: 'PYTHONPATH'

И после выполнения PYTHONPATH=/usr/lib/python2.7/dist-packages gnome-sudoku в терминале я добираюсь -

ImportError: /usr/lib/python2.7/dist-packages/gi/_gi.so: undefined symbol: PyUnicodeUCS4_AsUTF8String

Моя версия Python 2.7.4, как можно продолжить двигаться?