Finalmente encontré la respuesta cuando descubrí que un script diferente que había ejecutado con éxito muchas veces ya no funcionaba.
Cambié la intercalación en mi base de datos de utf8_general_ci a utf8_bin. Hay un error en MySQLdb 1.2.3 que hace que las cadenas utf8_bin no se reconozcan como texto, por lo que la conversión Unicode no se realiza. Esto se solucionó en MySQLdb 1.2.4.
https://sourceforge.net/p/mysql-python/bugs/289/