Are you running MySQL on Debian or Ubuntu with InnoDB? You might want to disable /etc/mysql/debian-start. When you run /etc/init.d/mysql start it runs this script, which runs mysqlcheck, which can destroy performance.

It can happen on a server with MyISAM tables, if there are enough tables, but it is far worse on InnoDB. There are a few reasons why this happens -- access to open an InnoDB table is serialized by a mutex, for one thing, and the mysqlcheck script opens all tables. One at a time.