No need to downgrade MySQL, just open up your my.cnf/my.ini file, find the [mysqld] section, and add this underneath it:
old_passwords=1
After restarting your server, login via the CLI and execute this command:
SET PASSWORD FOR root@localhost = PASSWORD('your_pass_here');
Also note that you'll need to update the passwords for any previously-created users if you want PHP4 to use those accounts.
Basically, what you're doing is disabling the new hashing algorithm that was implemented into the login protocol as of MySQL 4.1. Then, the SET PASSWORD commands update the user table with differente hashes, because the PASSWORD() command now uses the old hasing algorithm.
EDIT: Besides, if you were going to the extreme of using different versions, I'd recommend upgrading PHP before I recommended downgraded MySQL.