в самом начале скрипта имееться это ?
#!/usr/bin/python
#-*- coding: utf-8 -*-

тут кстати заметил глюк в питоне , выше приведено указание кодировки работающее под виндами , п под линухом utf8 я пишу без дефиса что под вендой отказалось работать

кстати глюк у вас потому что вы забыли сначала декодировать строку перед тем как ее кормить encode() ,но это не отменяет необходимости указания кодировки вначале файла , смотрите код что я приводил ранее и поймете