For some unknown reason I decided to install MySQL 4.1 rather than an older version which is on my server… But none of my PHP scripts would connect to it…

Resulting in the following error:
Client does not support authentication protocol requested by server; consider upgrading MySQL client

What the hell does that mean!?!?

A little digging on the MySQL website produces the following piece of useful information:

The password hashing mechanism was updated in MySQL 4.1 to provide better security and to reduce the risk of passwords being intercepted. However, this new mechanism is understood only by the 4.1 server and 4.1 clients, which can result in some compatibility problems. A 4.1 client can connect to a pre-4.1 server, because the client understands both the old and new password hashing mechanisms. However, a pre-4.1 client that attempts to connect to a 4.1 server may run into difficulties.

Solution:
Use the following:
SET PASSWORD FOR 'some_user'@'some_host' = OLD_PASSWORD('mypass');
FLUSH PRIVILEGES

Useful links:
5.5.9 Password Hashing in MySQL 4.1
A.2.3 Client does not support authentication protocol