No indicas que versión de Mysql usas .. pero parace que usas una versión 4.1.x con PHP ?.?.? pero usas las funciones mysql_xxxx() para acceder a Mysql.. (eso es el "cliente" que menciona el error).
Bien .. si es ese el caso .. las contraseñas de los usuarios de Mysql las gestiona diferente las versiones 4.0 e inferiores (de Msyql) que la 4.1 y superiores .. Si no quieres complicarte .. debes cambiar los usuarios (sus contraseñas) de Mysql al formato antigüo de contraseñas.
http://www.forosdelweb.com/f18/error-1251-acceder-mysql-por-phpmyadmin-270030/
otra cosa que puedes hacer es usar Mysql 4.0 si realmente no piensas usar las funcionalidades de Mysql 4.1.x o por ejemplo por qué desarrollas "en casa" y luego tu trabajo queda en un servicio de hosting con Mysql 4.0.x o inferior .. (ahí no vale la pena usar una versión "superior" si luego no puedes usarla en tu servidor de "producción").
Un saludo,