Ahora esta mucho mejor explicado y justamente como pensaba, en el IDE tu programa corre bien por que, el bendito editor soporta unicode, por default.
Lo tienes que hacer es ajustar primero la consola para que funcione.
Esto es problema de tu linea de comando, python no tiene nada que ver aquí.