Acho que o problema está no arquivo fonte não ter codificação unicode.
Você pode colocar esse trecho logo no início do seu arquivo:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
Outra solução é usar python3
#Edit: Adicionada solução que resolveu o problema
reload(sys)
sys.setdefaultencoding('utf8')