Упираетесь ли Вы в ресурсы процессора - можно сказать по выводу команды top. Если MySQL съедает более 90% во время выполнения запроса (при условии, что у Вас одно ядро) - точно не хватает производительности процессора.
Посмотрите, не ушли ли Вы в SWAP - возможно, у Вас недостаточно оперативной памяти. Команда free -m или top
Запросы запросу рознь - если у Вас запрос состоит из десятка join, то тут не спасёт даже десяток ядер.
Вообще, 400МГц для веб-сервера - это мало.
Предоставьте информацию по конфигурации сервера и конфигурации MySQL, а также пример запроса. Конфиг MySQL у Вас дефолтный? С включением кеширования ситуация может измениться в лучшую сторону (при условии, что есть для этого достаточно ресурсов).
Можете включить лог медленных запросов - в конфиг mysql добавьте строчки
log-slow-queries=/var/log/slow_queries.log
long_query_time=3