LÖST!
Även om SET SESSION old_passwords=0;
fungerade inte i phpMyAdmin.
Jag laddade ner MySQL GUI-verktyg och använde MySQL Query Browser för att köra samma kommando på icke-DBO-användare:
SET SESSION old_passwords = 0;
SELECT @@global.old_passwords, @@session.old_passwords, Length(PASSWORD('abc'));
returneras nu:
1 0 41
Så jag ändrade helt enkelt lösenordet:
SET PASSWORD = PASSWORD('my_old_password')
Och nu ansluter PHP 5.4 PDO till databasen med den användaren!