I looked into Aaron's idea for comment  #2.  Here's the implementation I tried.

EXPLAIN ANALYZE WITH first AS (
  SELECT min(Revision.id) AS id
  FROM Revision JOIN BranchRevision ON BranchRevision.revision = Revision.id
  WHERE BranchRevision.branch = 152968 AND Revision.revision_date >= '2009-08-10 21:56:30.623339+00:00'
), last AS (
  SELECT max(Revision.id) AS id
  FROM Revision JOIN BranchRevision ON BranchRevision.revision = Revision.id
  WHERE BranchRevision.branch = 152968 AND Revision.revision_date <= '2009-08-11 23:51:08.021106+00:00'
)
SELECT
       BranchRevision.branch,
       BranchRevision.revision,
       BranchRevision.sequence,
       Revision.date_created,
       Revision.gpgkey,
       Revision.id,
       Revision.karma_allocated,
       Revision.log_body,
       Revision.revision_author,
       Revision.revision_date,
       Revision.revision_id
FROM BranchRevision,
     Revision
WHERE BranchRevision.branch = 152968
  AND BranchRevision.sequence IS NOT NULL
  AND BranchRevision.revision = Revision.id
  AND BranchRevision.revision >= (SELECT id FROM first)
  AND BranchRevision.revision <= (SELECT id FROM last);

 Nested Loop  (cost=363833.91..394623.20 rows=22 width=215) (actual time=1.974..1.980 rows=1 loops=1)
   CTE first
     ->  Aggregate  (cost=181916.93..181916.94 rows=1 width=4) (actual time=0.928..0.928 rows=1 loops=1)
           ->  Nested Loop  (cost=0.00..181862.47 rows=21781 width=4) (actual time=0.883..0.922 rows=1 loops=1)
                 ->  Index Scan using revisionnumber_branch_sequence_unique on branchrevision  (cost=0.00..30513.07 rows=21781 width=4) (actual time=0.012..0.102 rows=103 loops=1)
                       Index Cond: (branch = 152968)
                 ->  Index Scan using changeset_pkey on revision  (cost=0.00..6.94 rows=1 width=4) (actual time=0.007..0.007 rows=0 loops=103)
                       Index Cond: (public.revision.id = public.branchrevision.revision)
                       Filter: (public.revision.revision_date >= '2009-08-10 21:56:30.623339'::timestamp without time zone)
   CTE last
     ->  Aggregate  (cost=181916.93..181916.94 rows=1 width=4) (actual time=0.910..0.911 rows=1 loops=1)
           ->  Nested Loop  (cost=0.00..181862.47 rows=21781 width=4) (actual time=0.027..0.866 rows=103 loops=1)
                 ->  Index Scan using revisionnumber_branch_sequence_unique on branchrevision  (cost=0.00..30513.07 rows=21781 width=4) (actual time=0.012..0.072 rows=103 loops=1)
                       Index Cond: (branch = 152968)
                 ->  Index Scan using changeset_pkey on revision  (cost=0.00..6.94 rows=1 width=4) (actual time=0.006..0.006 rows=1 loops=103)
                       Index Cond: (public.revision.id = public.branchrevision.revision)
                       Filter: (public.revision.revision_date <= '2009-08-11 23:51:08.021106'::timestamp without time zone)
   InitPlan 3 (returns $2)
     ->  CTE Scan on first  (cost=0.00..0.02 rows=1 width=4) (actual time=0.932..0.933 rows=1 loops=1)
   InitPlan 4 (returns $3)
     ->  CTE Scan on last  (cost=0.00..0.02 rows=1 width=4) (actual time=0.911..0.912 rows=1 loops=1)
   ->  Index Scan using revisionnumber_branch_sequence_unique on branchrevision  (cost=0.00..30621.97 rows=22 width=12) (actual time=1.965..1.969 rows=1 loops=1)
         Index Cond: (branch = 152968)
         Filter: ((sequence IS NOT NULL) AND (revision >= $2) AND (revision <= $3))
   ->  Index Scan using changeset_pkey on revision  (cost=0.00..7.59 rows=1 width=203) (actual time=0.006..0.007 rows=1 loops=1)
         Index Cond: (public.revision.id = public.branchrevision.revision)
 Total runtime: 2.188 ms

That's several times faster than what we have now on a warm cache, but this bug is about a cold cache.  In the two lines like "Nested Loop  (cost=0.00..181862.47 rows=21781 width=4) (actual time=0.883..0.922 rows=1 loops=1),"  I don't know whether to be happy about the second "rows=1" or unhappy about the first "rows=21781".  I'll ask Robert or Stuart to weigh in.