I have been diagnosing a problem with the same issues as this using 1&1 (1and1.com) as the web host. I am happy to announce that I do not think that this is a web host issue, be it 1&1, Go Daddy or Dreamhost.
From my findings, stopping the site totally through htaccess deny from all, allowing just me, then the site loads in a few seconds compared to sometimes a minute.
Turning the site on again makes everything run slowly.
Doing a wget, running php locally via shell and other testing, it seems that the main page works ok (ish), only then going to an article from the main page takes the very long time. part of the article loads, showing the "by Kelly" and normal page headers, then the clock starts ticking, then the article is shown :
So the actual query to get the article is what is taking a long time. This server is set to a 60 second timeout, which I think may be been hit, however the article is still showing correctly.
Assuming that things work with just one user on the site ok ish, then this would make me think that with multiple users the tables are locked somehow for a read, or for logging of the browsers access, until the time out is reached and the site shows ok.
The mysql server does not show slow queries that would represent the normal page accesses, though it does show for a query that seems to be finding linked articles to the current article by some scoring method.
I am very lost currently, any advice will be appreciated.