MYSQL на одном ядре

luxs, explain'ом проанализируйте запросы http://www.mysql.ru/docs/man/EXPLAIN.html

Может индексов не хватает

mysqltuner.pl пройдитесь по настройкам mysql, может буферы слишком малы (на те же индексы к примеру)