Locale won't change a thing for whatever weird reason.

Try declaring the encoding by adding

#-*- coding: utf-8 -*-

after #!/usr/bin/python

and get rid of the .encode('utf-8') part everywhere. I think that will do the trick. If it does, let me know and I'll change it in github.