If You run CPU - you can tell by the top display. If MySQL eats up more than 90% during the query execution (assuming that You have a single core) - just not enough processor performance.
Look, I didn't leave You in a SWAP You may not have sufficient RAM. The command free-m or top
The queries request the strife - if You have a query consists of a join, then there will not save even dozens of cores.
In General, 400MHz for the web server is not enough.
Provide information on server configuration and MySQL configuration, as well as a sample request. MySQL config You default? With the inclusion of caching, the situation may change for the better (provided that there are enough resources for this).
Can turn on log slow queries in mysql config add the lines