Fandt endelig svaret, da jeg opdagede, at et andet script, jeg havde kørt med succes mange gange, ikke længere virkede.
Jeg havde ændret sorteringen i min database fra utf8_general_ci til utf8_bin. Der er en fejl i MySQLdb 1.2.3, der gør, at utf8_bin-strenge ikke genkendes som tekst, så unicode-konverteringen sker ikke. Dette blev rettet i MySQLdb 1.2.4.
https://sourceforge.net/p/mysql-python/bugs/289/