После замечания Ravilr-а о переходе на Python 3 решил посмотреть, что сейчас работает с 3.1.2, а что - нет. Итак:

• Ядро пакета: после ряда правок будет работать
• Модуль pywin32 (WinAPI в python-е): есть готовый пакет под 3.1
• Модуль py2exe: фиг там. Я попробовал пересобрать под 3.1 из исходников - фиг с два (поменялось API самого Python-а). Ждём пока (если) разработчики портируют.
• mysql-python: разработчики не спешат портировать модуль под 3.х
• PMW (Pythom MegaWidgets - дополнительные контролы для PyGTK): должно работать без вопросов

Но вообще, перейти на 3.1 хотелось бы - там наконец объединили "строку" и "unicode-строку", теперь (по идее) можно будет нормально работать.
------------ Дoбавленo в 11.59:
Update: существует кроссплатформенный родственник py2exe по имени cx_freze. Попробую перейти на него.
------------ Дoбавленo в 12.07:
Update2: Мини-опрос про создание exe-файлов!
[vote=Генерировать...]
[answer=py-скрипт, ибо нефиг]
[answer=Полностью автономный exe]
[answer=Автономный exe с отделённым runtime-ом (zip, класть рядом с exe)]
[/vote]