Is your Python curses module linked to libncurses.so.5 or libncursesw.so.5? Example:

$ ldd /usr/lib/python2.7/lib-dynload/_cursesmodule.so |grep curses
	libncursesw.so.5 => /lib/libncursesw.so.5 (0x00375000)

libncursesw has a much better support of Unicode than libncurses.

Since Python 3.3, the Python curses.window.addstr() method uses waddwstr() when the module is linked to libncursesw, which also improves the Unicode support.