If the queries are very large, very complex, or operate on very large tables, this could be an issue. If there are domain aggregate functions that fail silently when the query executes, this could be the problem also. Maybe lookups or calculated fields are bombing? Have you checked the queries' tables to make sure they are still intact, and that field names have not somehow inadvertently changed?
When everything is coming your way, you're in the wrong lane.