RISOLTO!
Sebbene SET SESSION old_passwords=0;
non funzionava in phpMyAdmin.
Ho scaricato gli Strumenti della GUI di MySQL e ha utilizzato MySQL Query Browser per eseguire lo stesso comando su utenti non DBO:
SET SESSION old_passwords = 0;
SELECT @@global.old_passwords, @@session.old_passwords, Length(PASSWORD('abc'));
ora restituito:
1 0 41
Quindi ho semplicemente cambiato la password:
SET PASSWORD = PASSWORD('my_old_password')
E ora PHP 5.4 PDO si connette al database con quell'utente!