Tohle mi chodí, ale mám nastavený jak vstup, tak výstup na terminalu na UTF-8 a samozřejmě text programu je také v UTF-8

[gilhad@merleAvr(7) ~]$ cat xx.py 
#!/usr/bin/python -u
# vim: fileencoding=utf-8:nomodified:nowrap:textwidth=0:foldmethod=marker:foldcolumn=4:ruler:showcmd:lcs=tab\:|- list:noexpandtab:nosmarttab:softtabstop=0
test=u"Příliš žluťoučký kůň úpěl ďábelské ódy"
print test

[gilhad@merleAvr(7) ~]$ python xx.py 
Příliš žluťoučký kůň úpěl ďábelské ódy