Установите python-gnome2, которые предоставляют модуль gnome.ui. Я думаю, это должно работать.
Так что
sudo apt-get install python-gnome2