Hace poco tuve un problema similar y me parece que puede ser un problema de php5. En realidad, no es un "problema", pero a partir de php5, las funciones mysql_* no vienen por defecto con la instalación (en su lugar, está mysqli_*).
Lo que tendrías que hacer (suponiendo que tengas Windows) es ir a php.net y buscar los binarios de la versión de php que tengas (exactamente la misma: por ej. 5.0.4, no 5; la url es
http://www.php.net/releases.php).
Bajás el zip y buscás un archivo "php_mysql.dll" (dentro de la carpeta "ext", al menos en el zip que bajé yo). Ese tiene que ir al directorio donde están las extensiones de php. (Ej: C:\Apache\php\ext)
Además, dentro del directorio php del .zip, tendría que estar este otro archivo, que también viene en el paquete: "libmysql.dll". Tendrías que pasarlo al directorio php de tu instalación.
No sé si se aplicará a tu caso, pero yo tengo instalado el wamp y nunca tuve problemas porque esas .dll ya las tenía en la instalación, pero cuando empecé a usar Zend Studio, que instala internamente php para su propio uso yte da la opción de usar php4 y php5, en php5 ninguna función mysql_ me funcionaba. Entonces tuve que bajarme ese zip e instalar (guardar) las 2 .dll en dos directorios distintos: uno, el de la instalación del Zend, y otro, el system32 de windows (que está, por ej. en C:\DIRECTORIO_DE_WINDOWS\SYSTEM32\)
Bueno, no sé si será eso, pero a mí me volvió loco. Me parece que tal vez viene por ahí la cosa. (Una sugerencia: para sacarte las dudas, podrías probar las funciones mysqli_*, que son muy parecidas en la sintaxis a las mysql_*. Si andan bien, quiere decir que el problema es que tenés las .dll, pero el server MySQL está ok)
Suerte
Califa