RESOLVIDO!
Embora o
SET SESSION old_passwords=0; não estava funcionando no phpMyAdmin. Baixei as Ferramentas de GUI do MySQL e usei o MySQL Query Browser para executar o mesmo comando em um usuário não DBO:
SET SESSION old_passwords = 0; SELECT @@global.old_passwords, @@session.old_passwords, Length(PASSWORD('abc')); agora retornou:
1 0 41
Então eu simplesmente mudei a senha:
SET PASSWORD = PASSWORD('my_old_password') E agora o PHP 5.4 PDO se conecta ao banco de dados com esse usuário!