This line really stands out:
Generated in 35.099 seconds in which 0.048 seconds were spent on a total of 7 queries. Zlib compression disabled.
MySQL is generating everything very quick, but the actual processing of the page itself is taking a long time. It could be that they have you pointed at a MySQL database on a different server, and the actual server your site is running on just has a very high load on it.
Needless to say, those numbers aren't something we see too often. Usually if there's a slowdown it's going to be on the MySQL side.
