Isso parece um caso de codificação dupla; Não tenho muita experiência com Python, mas tente ajustar as configurações de conexão do MySQL conforme o conselho em http://tahpot.blogspot.com/2005/06/mysql-and-python-and-unicode.html

O que estou supondo que está acontecendo é que a conexão é latin1, então o MySQL tenta codificar a string novamente antes do armazenamento no campo UTF-8. O código lá, especificamente este bit:

é provavelmente o que você quer.