Two fast queries get slow when combined

I have two small queries which are both very fast to evaluate
separately. The first query, "Query 1", calculates some statistics and
the the second query, "Query 2", finds a subset of relevant keys.
When combined into a single query which calculates statistics from only
the subset of relevant keys the evaluation plan explodes and uses both
seq scans and bitmap heap scans.
How can I improve the performance of the combined query?

Queries and output from EXPLAIN ANALYZE can be seen here with some
syntax highlighting:
    http://rafb.net/p/BJIW4p69.html

I will also paste it here:

=============================================================================
QUERY 1 (very *fast*):
=============================================================================
SELECT keyId, count(1) as num_matches
FROM stats
GROUP BY keyId
LIMIT 50

  Limit  (cost=0.00..23.65 rows=50 width=8) (actual time=0.090..2.312
rows=50 loops=1)
    ->  GroupAggregate  (cost=0.00..4687.46 rows=9912 width=8) (actual
time=0.085..2.145 rows=50 loops=1)
          ->  Index Scan using stats_keyId on stats  (cost=0.00..3820.19
rows=99116 width=8) (actual time=0.031..1.016 rows=481 loops=1)
  Total runtime: 2.451 ms
(4 rows)


=============================================================================
QUERY 2 (very *fast*):
=============================================================================
SELECT keyId, sortNum
FROM items i
WHERE sortNum > 123
ORDER BY sortNum
LIMIT 50

  Limit  (cost=0.01..9.87 rows=50 width=8) (actual time=0.068..0.610
rows=50 loops=1)
    InitPlan
      ->  Limit  (cost=0.00..0.01 rows=1 width=0) (actual
time=0.009..0.025 rows=1 loops=1)
            ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual
time=0.006..0.007 rows=1 loops=1)
    ->  Index Scan using items_sortNum on items i  (cost=0.00..1053.67
rows=5344 width=8) (actual time=0.063..0.455 rows=50 loops=1)
          Index Cond: (sortNum >= $0)
  Total runtime: 0.749 ms
(7 rows)



=============================================================================
COMBINED QUERY (very *slow*):
=============================================================================
   SELECT keyId, sortNum, count(1)
   FROM stats s, items i
   WHERE s.keyId = i.keyId AND i.sortNum > 123
   GROUP BY i.keyId, i.sortNum
   ORDER BY i.sortNum
   LIMIT 50

Limit  (cost=3281.72..3281.84 rows=50 width=16) (actual
time=435.838..436.043 rows=50 loops=1)
    InitPlan
      ->  Limit  (cost=0.00..0.01 rows=1 width=0) (actual
time=0.016..0.021 rows=1 loops=1)
            ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual
time=0.012..0.013 rows=1 loops=1)
    ->  Sort  (cost=3281.71..3289.97 rows=3304 width=16) (actual
time=435.833..435.897 rows=50 loops=1)
          Sort Key: i.sortNum
          ->  Hash Join  (cost=2745.80..3088.59 rows=3304 width=16)
(actual time=364.247..413.164 rows=8490 loops=1)
                Hash Cond: (s.keyId = i.keyId)
                ->  HashAggregate  (cost=2270.53..2394.43 rows=9912
width=8) (actual time=337.869..356.533 rows=9911 loops=1)
                      ->  Seq Scan on items  (cost=0.00..1527.16
rows=99116 width=8) (actual time=0.016..148.118 rows=99116 loops=1)
                ->  Hash  (cost=408.47..408.47 rows=5344 width=12)
(actual time=26.342..26.342 rows=4491 loops=1)
                      ->  Bitmap Heap Scan on items i
(cost=121.67..408.47 rows=5344 width=12) (actual time=5.007..16.898
rows=4491 loops=1)
                            Recheck Cond: (sortNum >= $0)
                            ->  Bitmap Index Scan on items_sortNum
(cost=0.00..120.33 rows=5344 width=0) (actual time=4.273..4.273
rows=13375 loops=1)
                                  Index Cond: (sortNum >= $0)
Total runtime: 436.421 ms
(16 rows)