It probably is a host issue. Assuming that you’re relatively stock WordPress, the queries shouldn’t be so inefficient that they’re causing timeouts.
When it says a “remote mysql database”, does that mean a remote database server with the same hosting company, or does it mean you’re using a database server that’s physically located somewhere else? If the latter, that could be your problem. Negotiating a MySQL connection then running a query requires a fair number of roundtrips, so if there’s a lot of latency it could add up fast to approach the timeout.
Based on the rather canned-looking reply from the host, I’m willing to bet you’re using some low-priced shared hosting. Unfortunately, almost all of those are terrible. After a year or two of having problem after problem with shared hosts, I gave up and went to a good VPS and have had no issues since. This may not be a problem for you though, if you’re not willing and able to manage an entire virtual server for one small blog.