It seems that it is not a WordPress problem; its roots are deeper, in PHP configuration...
Create a *.php file (it doesn't matter what you call it and where you put it, but let's say you called it test.php and it is located in your site's root directory). In that file, write just this one line:
<?php phpinfo(); ?>
Then run this script as http://yoursite.com/test.php; it will produce a lot of technical information about your PHP installation. Look for mysql in the output. If you have MySQL extention enabled, you will see a table listing different settings for it, something like this (in a table format):
MySQL Support enabled
Active Persistent Links 0
Active Links 0
Client API version 5.0.18
If you see no references to MySQL in the phpinfo() output, contact your hosting company and ask them to figure out why your PHP installation is not configured for MySQL access (it's possible that you have a hosting plan that doesn't have this feature, so you may have to upgrade).