Hab herrausgefunden woran es liegt. Ab MySQL v4.1 benutzt der Server eine neue Passwort hash Funktion, die MySQLdb aber "noch" nicht unterstützt(1251, 'Client does not support authentication protocol requested by server; consider upgrading MySQL client')
Als work-a-round kann man den Server mit dem Parameter "--old-passwords" starten oder besser, man erstell einen neuen Benutzter und nutzt OLD_PASSWORD(). Wie das geht steht hier: http://dev.mysql.com/doc/mysql/en/old-client.html