MySQLdb.connect accetta un parametro use_unicode, che potrebbe risolvere il problema. In caso contrario, potresti anche dover impostare il set di caratteri su qualsiasi cosa utilizzi la tua tabella:
MySQLdb.connect(host="localhost", user="root",passwd="*****", use_unicode=True, charset='xxxxx')
http://mysql-python.sourceforge.net/MySQLdb.html
