This does seem like a case of double-encoding; I don't have much experience with Python, but try adjusting the MySQL connection settings as per the advice at http://tahpot.blogspot.com/2005/06/mysql-and-python-and-unicode.html
What I'm guessing is happening is that the connection is latin1, so MySQL tries to encode the string again before storage to the UTF-8 field. The code there, specifically this bit:
EDIT: With Python when establishing a database connection add the following flag: init_command='SET NAMES utf8'.
In addition set the following in MySQL's my.cnf: default-character-set = utf8
is probably what you want.