Linking this because the author of the post doesn’t allow comments, but hopefully checks referers, and because this is a common problem people are going to run into.
The solution is to do what django.contrib.markup does with its textile filter:
force_unicode(textile.textile(smart_str(value), encoding='utf-8', output='utf-8'))
This makes use of the smart_str and force_unicode functions from django.utils.encoding, both of which are mentioned in Django’s Unicode documentation, and which are provided for pretty much this exact purpose.
Obligatory self-plug: template_utils trunk has supported this for a while (I had to Unicode-ify it when I did the re-launch of this site).