Вам нужно понять в какой момент возникла не-юникод кодировка. Попробуйте вместо скрипта из PHP запустить echo "ваша кириллица" >> test.txt
Если в файле будут "кракозябры" - то проблема где-то до вызова Python, если все норм, то - после. Сам Python без явного вызова функций перекодировки ничего менять не станет. Но тут все зависит, от того, что вы делаете в этом скрипте. Так же вы не написали, как и куда возвращается значение.
PS А что у вас в /etc/default/locale?