Check out phpinfo to see if the mysql functions are compiled with your PHP
<?php
phpinfo();
?>
Since in some versions of php, its not default with the install.
Edit for the Update:
You should have a full MySQL category in your phpinfo();
See this for example: https://secure18.easycgi.com/phpinfo.php (googled example)