There are a number of things you can do on this front, both in testing and in tweaking the performance.
On testing one of the first things you should do is enable the core "Database logging" module which will help you find hidden errors in the system (it could be a bunch of php errors caused by missing php extensions or bad settings). It could also be the database connection and this can record the queries so that you can run them manually. You should also enable the core "Syslog" module.
The Devel module also includes a few other modules including performance logging and code review, both of which can help with the troubleshooting problem.
The next thing you should do is setup a test lamp environment on your local machine (your computer) that has the same php settings and extensions and see if it has the same problem. If it does then the problem may not have anything to do with the database.
Now on to improving overall performance...
First you will want to enable the "Throttle" core module. This will enable content throttling. The primary thing you can do though is in admin > Site Configuration > Performance you should enable the normal caching mode. Also enable page compression and optimize the CSS and JS.
Another tool that might help your site user experience a bit is using the ImageCache module to deliver custom sized, cached images.
Then there is PressFlow. Now this is actually a custom build of the Drupal core files that are optimized specifically for use in PHP 5 only and with only MySQL. It uses improved function calling and structures as well as improved database queries. To use it you simply download the version that is compatible with your version of Drupal and replace your core Drupal files with PressFlow's. As they say on their site "Pressflow makes Drupal scale".
Check out Pressflow here: http://fourkitchens.com/pressflow-makes-drupal-scale
I hope that helps!