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!