PHP usa las extensiones para Mysql 4.0.x e inferiores que son las que te ofrecen las funciones: msyql_xxx()
Para Msyql 4.1.x en adelante .. los nuevos "clientes" son las extensiones mysqli_xxxx() ..
www.php.net/mysqli .. pero esas extensiones sólo funcionan para PHP 5 ..
Soluciones:
1) Cambias la versión de PHP a la 5 y usas las extensiones mysqli (pero también las mysql para compatibilidad con tus anteriores aplicaciones).
http://www.php.net/mysqli
2) Te quedas como estás .. pero migras tus contraseñas de Mysql al formato antigüo de Mysql 4.x e inferiores.
http://dev.mysql.com/doc/mysql/en/Password_hashing.html
Un saludo,