Zdá se, že jde o případ dvojitého kódování; S Pythonem moc zkušeností nemám, ale zkuste upravit nastavení připojení MySQL podle rady na http://tahpot.blogspot.com/2005/06/mysql-and-python-and-unicode.html
Hádám, že se děje to, že spojení je latin1, takže se MySQL pokouší znovu zakódovat řetězec před uložením do pole UTF-8. Kód tam, konkrétně tento bit:
je pravděpodobně to, co chcete.