Μάλλον το πρόβλημα το έχεις με τα Windows... γιατί αυτά είναι τα "μόνα" που δεν δουλεύουν με utf-8...
Αν γράφεις απλά το u μπροστά από κάθε string λογικά δεν θα έχεις πρόβλημα...
δηλαδή αντί για "Γεια σου κόσμε!" γράψε u"Γεια σου κόσμε!"...
Για παράδειγμα τρέξε:
from Tkinter import *
root = Tk()
w = Label(root, text = u"Γειά σου κόσμε!")
w.pack()
root.mainloop()
Βέβαια δε βάζω και το χέρι μου στη φωτιά ότι είναι τόσο απλό... γιατί python σε windows δεν έχω γράψει και πολλές φορές... πόσο μάλλον να θέλω ελληνικά (ποτέ)...
Σε linux και σε mac μπορείς να τα τρέξεις κατευθείαν...
Επίσης μπορείς αν δε κάνω λάθος να γράψεις στη πρώτη γραμμή του κώδικα σου κάτι και ότι γράφεις σε string από εκεί και κατω να το παίρνει από default σε unicode... αλλά δε θυμάμαι τι πρέπει να γράψεις...!!! (τώρα σε βοήθησα
)
Αν το πρόβλημα μένει πες μου και θα το κοιτάξω καλύτερα...!