ROZWIĄZANE!
Chociaż SET SESSION old_passwords=0;
nie działał w phpMyAdmin.
Pobrałem Narzędzia GUI MySQL i użył przeglądarki MySQL Query Browser do wykonania tego samego polecenia na użytkowniku innym niż DBO:
SET SESSION old_passwords = 0;
SELECT @@global.old_passwords, @@session.old_passwords, Length(PASSWORD('abc'));
teraz zwrócone:
1 0 41
Więc po prostu zmieniłem hasło:
SET PASSWORD = PASSWORD('my_old_password')
A teraz PHP 5.4 PDO łączy się z bazą danych z tym użytkownikiem!