Hittade äntligen svaret när jag upptäckte att ett annat skript som jag hade kört framgångsrikt många gånger inte längre fungerade.
Jag hade ändrat sorteringen i min databas från utf8_general_ci till utf8_bin. Det finns en bugg i MySQLdb 1.2.3 som gör att utf8_bin-strängar inte känns igen som text, så unicode-konverteringen sker inte. Detta fixades i MySQLdb 1.2.4.
https://sourceforge.net/p/mysql-python/bugs/289/