I tried on Mac OSX.
$ echo $LANG
en_US.utf-8
$ python3
Python 3.3.2 (default, Aug 22 2013, 12:33:42)
[GCC 4.2.1 Compatible Apple Clang 4.0 ((tags/Apple/clang-421.0.60))] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> from unidecode import unidecode
>>> print(unidecode(u"Cœur"))
Coeur
>>> print(unidecode(u"сообще́ния"))
soobshcheniia
You may try setting the LANG variable.