MySQLdb.connectはuse_unicodeパラメータを取ります。これにより、問題が解決する場合があります。そうでない場合は、テーブルで使用されているものに文字セットを設定する必要がある場合もあります。
MySQLdb.connect(host="localhost", user="root",passwd="*****", use_unicode=True, charset='xxxxx')
http://mysql-python.sourceforge.net/MySQLdb.html