The problem is that paginate uses :limit and :offset which can't work well with eager joins (your :include => 'tags') since all the matching rows (perhaps thousands or millions) have to be pulled into Ruby, parsed, then limited and offset. To put it mildly, this does not scale.
Remove the :include => tags to regain nearly all your performance at the minor cost of 12 additional queries to pull tags per page.
Generally speaking, to troubleshoot database issues, look at the slow queries in your production.log and use EXPLAIN <the query> in MySQL to see why they're performing poorly. Luckily, in this case, it's just a matter of returning way too much data.
jeremy