Per risolverlo velocemente puoi semplicemente aggiornare PHP all'ultima versione (es. PHP 5.2.5), soprattutto visto che il supporto per PHP 4 è stato messo in stato "discontinued" dal 31 dicembre scorso.

In alternativa devi configurare MySQL per avviarsi utilizzando il vecchio algoritmo di hashing delle password (vedi http://dev.mysql.com/doc/refman/5.0/en/old-client.html)