Okay, I'm really confused now.
I just did a
SELECT user FROM User WHERE password = PASSWORD('my password');
and got nothing. When I did:
SELECT user FROM User WHERE password = OLD_PASSWORD('my password');
I got 'root' back. I can't see how to request phpMyAdmin use the old_password function, but then maybe mysql_connect() automatically uses it? In any case I can't work out why it can't connect if my root user already has the OLD_PASSWORD() functionality.
Any ideas? Cheers