By turning everything into unicode objects (unicode(string)) and then running body.encode('utf-8') and using quoted printable, it works. Thanks for all the help, it's really appreciated!