MAV, мои эксперименты показали, что технически невозможно сделать такую поддержку кириллицы (в консоли), чтобы работало и под Windows, и под Linux.

Для Windows надо перекодировать выходной файл в CP866 (OEM), тогда кириллица в консоли будет. Сделать "компилятор", выполняющий это действие, можно за <~ 5 минут с помощью пакета Delphi.

Для Linux (по крайней мере - для Ubuntu 9.04) нужна кодировка UTF-8. Опять таки, перекодировщие собирается за то же время.

Я, за-ради универсальности, не стал включать ни ту, ни другую опцию в пакет. Предлагаю (опять-таки) проголосовать.

ГОЛОСОВАЛКА
Какую кодировку использовать для выходного файла:

• CP1251 (текущая ситуация)
• CP866 (чтобы кириллица работала в Windows, но не в Linux)
• UTF8 (чтобы кириллица работала в Linux, но не в Windows)

Для владеющих английским - баг репорт на сайте Python-а: клац.