¡SOLUCIONADO!
Aunque SET SESSION old_passwords=0;
no funcionaba en phpMyAdmin.
Descargué las Herramientas GUI de MySQL y usó MySQL Query Browser para ejecutar el mismo comando en un usuario que no es DBO:
SET SESSION old_passwords = 0;
SELECT @@global.old_passwords, @@session.old_passwords, Length(PASSWORD('abc'));
ahora devuelto:
1 0 41
Así que simplemente cambié la contraseña:
SET PASSWORD = PASSWORD('my_old_password')
¡Y ahora PHP 5.4 PDO se conecta a la base de datos con ese usuario!