The query that failed in qastaging (comment 13) was significantly different than the one that Robert showed in comment 11.  In addition to an extraneous WITH clause at the very beginning of the whole query, the problematic structural subscription unioned query has the pertinent differences.

The query as found in qastaging was this.  It consistently takes over 35 seconds on staging.

  WITH ss as (SELECT * from StructuralSubscription
 WHERE StructuralSubscription.subscriber = 343381)
 SELECT BugTask.assignee, BugTask.bug, BugTask.bugwatch, BugTask.date_assigned, BugTask.date_closed, BugTask.date_confirmed, BugTask.date_fix_committed, BugTask.date_fix_released, BugTask.date_incomplete, BugTask.date_inprogress, BugTask.date_left_closed, BugTask.date_left_new, BugTask.date_triaged, BugTask.datecreated, BugTask.distribution, BugTask.distroseries, BugTask.heat, BugTask.id, BugTask.importance, BugTask.milestone, BugTask.owner, BugTask.product, BugTask.productseries, BugTask.sourcepackagename, BugTask.status, BugTask.statusexplanation, BugTask.targetnamecache 
 FROM BugTask 
 LEFT JOIN Product ON BugTask.product = Product.id AND Product.active, Bug 
 WHERE Bug.id = BugTask.bug AND ((BugTask.status = 10) OR (BugTask.status = 15) OR (BugTask.status = 20) OR (BugTask.status = 21) OR (BugTask.status = 22) OR (BugTask.status = 25)) AND Bug.duplicateof is NULL AND Bug.latest_patch_uploaded IS NOT NULL AND BugTask.id IN (
 SELECT DISTINCT BugTask.id
 FROM BugTask
 LEFT JOIN Product ON (
 BugTask.product = Product.id AND Product.active)
 LEFT JOIN ss ss1 ON BugTask.product = ss1.product
 LEFT JOIN ss ss2 ON BugTask.productseries = ss2.productseries
 LEFT JOIN ss ss3 ON Product.project = ss3.project
 LEFT JOIN ss ss4 ON (
 BugTask.distribution = ss4.distribution AND (
 BugTask.sourcepackagename = ss4.sourcepackagename OR
 ss4.sourcepackagename IS NULL))
 LEFT JOIN ss ss5 ON BugTask.distroseries = ss5.distroseries
 LEFT JOIN ss ss6 ON BugTask.milestone = ss6.milestone
 WHERE
 NULL_COUNT(ARRAY[ss1.id, ss2.id, ss3.id,
 ss4.id, ss5.id, ss6.id]) < 6)
 AND (Bugtask.product IS NULL OR Product.active = TRUE) AND 
 (Bug.private = FALSE OR EXISTS (
 SELECT BugSubscription.bug
 FROM BugSubscription, TeamParticipation
 WHERE TeamParticipation.person = 6874 AND
 TeamParticipation.team = BugSubscription.person AND
 BugSubscription.bug = Bug.id
 UNION
 SELECT BugTask.bug
 FROM BugTask, TeamParticipation
 WHERE TeamParticipation.person = 6874 AND
 TeamParticipation.team = BugTask.assignee AND
 BugTask.bug = Bug.id
 ));

Recasting this to the spelling Robert gave, I get the following, which takes around 1 second on staging.

WITH ss as (SELECT * from StructuralSubscription
 WHERE StructuralSubscription.subscriber = 343381)
 SELECT DISTINCT BugTask.assignee, BugTask.bug, BugTask.bugwatch, BugTask.date_assigned, BugTask.date_closed, BugTask.date_confirmed, BugTask.date_fix_committed, BugTask.date_fix_released, BugTask.date_incomplete, BugTask.date_inprogress, BugTask.date_left_closed, BugTask.date_left_new, BugTask.date_triaged, BugTask.datecreated, BugTask.distribution, BugTask.distroseries, BugTask.heat, BugTask.id, BugTask.importance, BugTask.milestone, BugTask.owner, BugTask.product, BugTask.productseries, BugTask.sourcepackagename, BugTask.status, BugTask.statusexplanation, BugTask.targetnamecache
 FROM BugTask
 inner join bug on bug.id=bugtask.bug
 LEFT JOIN Product ON (BugTask.product = Product.id AND Product.active)
 LEFT JOIN ss ss1 ON BugTask.product = ss1.product
 LEFT JOIN ss ss2 ON BugTask.productseries = ss2.productseries
 LEFT JOIN ss ss3 ON Product.project = ss3.project
 LEFT JOIN ss ss4 ON (BugTask.distribution = ss4.distribution AND (
 BugTask.sourcepackagename = ss4.sourcepackagename OR ss4.sourcepackagename IS NULL))
 LEFT JOIN ss ss5 ON BugTask.distroseries = ss5.distroseries
 LEFT JOIN ss ss6 ON BugTask.milestone = ss6.milestone
 WHERE
    ((BugTask.status = 10) OR (BugTask.status = 15) OR (BugTask.status = 20) OR (BugTask.status = 21) OR (BugTask.status = 22) OR (BugTask.status = 25))
     AND Bug.duplicateof is NULL
     AND Bug.latest_patch_uploaded IS NOT NULL
     AND (Bugtask.product IS NULL OR Product.active = TRUE)
     AND 
 (Bug.private = FALSE OR EXISTS (
 SELECT BugSubscription.bug
 FROM BugSubscription, TeamParticipation
 WHERE TeamParticipation.person = 6874 AND
 TeamParticipation.team = BugSubscription.person AND
 BugSubscription.bug = Bug.id
 UNION
 SELECT BugTask.bug
 FROM BugTask, TeamParticipation
 WHERE TeamParticipation.person = 6874 AND
 TeamParticipation.team = BugTask.assignee AND
 BugTask.bug = Bug.id
 ))
AND NULL_COUNT(ARRAY[ss1.id, ss2.id, ss3.id, ss4.id, ss5.id, ss6.id]) < 6;

The EXISTS clause is not something Robert had, but I suspect it is necessary for non-anonymous users, and in my experiments removing it saved between .05 to .15 seconds.  My conclusion is that we can tweak that later as necessary: I should try to get a SQL syntax closer to the one Robert found in order to get the performance benefits he found.