A little help interpreting a query plan

We have the following query...

(SELECT COUNT(DISTINCT clm.id)
       FROM claims clm
       WHERE (clm.deleted = 0 and clm.status >=0)
       AND (clm.document_type = 0)
       AND (clm.assigned_ddr is null or clm.assigned_ddr = 537)
       AND clm.group_plan_id is not null
       and clm.group_plan_id > 0 and clm.reviewed is null and
clm.eob_id is null
       and clm.paid_eob is null and clm.mailed is null and
clm.approved_pay is null and clm.denied_pay is null
       AND (not exists (select * from claim_entries ce
                                where clm.id = ce.claim_id
                                       and left(ce.cpt_code,1) = '8'))
       AND ((clm.nea_number is not null and trim(clm.nea_number) <> '')
            or ((transmission_method='O'
                 and exists (select 1 from claim_attachments ca where
ca.claim_id = clm.id)))
            or (select count(1) from claim_attachments ca where
ca.claim_id = clm.id) > 1
            or clm.radiographs > 0))

We have two copies of roughly* the same database (in a single
cluster), and on one of them, the query above runs much faster and
postgresql produces a different query plan for each one.  It actually
returns the same results in both instances.  Can anyone think of why
there is such a difference in performance?

The following is the output of EXPLAIN ANALYZE for the fast DB.

 Aggregate  (cost=257280.93..257280.94 rows=1 width=4) (actual
time=2008.181..2008.181 rows=1 loops=1)
 ->  Nested Loop Anti Join  (cost=20733.11..257270.52 rows=4162
width=4) (actual time=1955.633..2008.053 rows=92 loops=1)
       ->  Bitmap Heap Scan on claims clm  (cost=20733.11..217377.24
rows=4242 width=4) (actual time=1926.553..2005.151 rows=145 loops=1)
             Recheck Cond: ((paid_eob IS NULL) AND (approved_pay IS
NULL) AND (eob_id IS NULL))
             Filter: ((group_plan_id IS NOT NULL) AND (reviewed IS
NULL) AND (mailed IS NULL) AND (denied_pay IS NULL) AND (status >= 0)
AND ((assigned_ddr IS NULL) OR (assigned_ddr = 537)) AND
(group_plan_id > 0) AND (deleted = 0) AND (document_type = 0) AND
(((nea_number IS NOT NULL) AND (btrim((nea_number)::text) <>
''::text)) OR ((transmission_method = 'O'::bpchar) AND (SubPlan 1)) OR
((SubPlan 2) > 1) OR (radiographs > 0)))
             ->  BitmapAnd  (cost=20733.11..20733.11 rows=10701
width=0) (actual time=242.331..242.331 rows=0 loops=1)
                   ->  Bitmap Index Scan on claims_paid_eob
(cost=0.00..3916.88 rows=211788 width=0) (actual time=34.637..34.637
rows=209892 loops=1)
                         Index Cond: (paid_eob IS NULL)
                   ->  Bitmap Index Scan on claims_approved_pay
(cost=0.00..8248.79 rows=446442 width=0) (actual time=132.734..132.734
rows=443655 loops=1)
                         Index Cond: (approved_pay IS NULL)
                   ->  Bitmap Index Scan on claims_eob_id
(cost=0.00..8563.75 rows=463371 width=0) (actual time=66.685..66.685
rows=457030 loops=1)
                         Index Cond: (eob_id IS NULL)
             SubPlan 1
               ->  Index Scan using claim_attachments_claim on
claim_attachments ca  (cost=0.00..10.10 rows=2 width=0) (actual
time=0.004..0.004 rows=0 loops=1741)
                     Index Cond: (claim_id = clm.id)
             SubPlan 2
               ->  Aggregate  (cost=10.11..10.12 rows=1 width=0)
(actual time=0.025..0.025 rows=1 loops=3696)
                     ->  Index Scan using claim_attachments_claim on
claim_attachments ca  (cost=0.00..10.10 rows=2 width=0) (actual
time=0.021..0.022 rows=0 loops=3696)
                           Index Cond: (claim_id = clm.id)
       ->  Index Scan using claim_entries_claim_id on claim_entries
ce  (cost=0.00..9.40 rows=1 width=4) (actual time=0.017..0.017 rows=0
loops=145)
             Index Cond: (clm.id = claim_id)
             Filter: ("left"((cpt_code)::text, 1) = '8'::text)
Total runtime: 2008.337 ms

And this is the same output for the slow DB...

Aggregate  (cost=113740056.63..113740056.64 rows=1 width=4) (actual
time=144707.698..144707.699 rows=1 loops=1)
 ->  Nested Loop Anti Join  (cost=162675.34..113740046.61 rows=4007
width=4) (actual time=92911.813..144707.465 rows=92 loops=1)
       ->  Bitmap Heap Scan on claims clm
(cost=162675.34..113701598.25 rows=4084 width=4) (actual
time=83998.175..144259.558 rows=145 loops=1)
             Recheck Cond: ((paid_eob IS NULL) AND (approved_pay IS
NULL) AND (eob_id IS NULL) AND (denied_pay IS NULL) AND (document_type
= 0) AND (status >= 0) AND (group_plan_id IS NOT NULL) AND
(group_plan_id > 0))
             Filter: ((reviewed IS NULL) AND (mailed IS NULL) AND
((assigned_ddr IS NULL) OR (assigned_ddr = 537)) AND (deleted = 0) AND
(((nea_number IS NOT NULL) AND (btrim((nea_number)::text) <>
''::text)) OR ((transmission_method = 'O'::bpchar) AND (SubPlan 1)) OR
((SubPlan 2) > 1) OR (radiographs > 0)))
             ->  BitmapAnd  (cost=162675.34..162675.34 rows=7389
width=0) (actual time=3208.242..3208.242 rows=0 loops=1)
                   ->  Bitmap Index Scan on claims_paid_eob
(cost=0.00..3891.55 rows=210544 width=0) (actual time=96.186..96.186
rows=209892 loops=1)
                         Index Cond: (paid_eob IS NULL)
                   ->  Bitmap Index Scan on claims_approved_pay
(cost=0.00..8200.57 rows=443747 width=0) (actual time=258.312..258.312
rows=443655 loops=1)
                         Index Cond: (approved_pay IS NULL)
                   ->  Bitmap Index Scan on claims_eob_id
(cost=0.00..8389.46 rows=453998 width=0) (actual time=182.446..182.446
rows=457030 loops=1)
                         Index Cond: (eob_id IS NULL)
                   ->  Bitmap Index Scan on claims_denied_pay
(cost=0.00..31890.19 rows=1726096 width=0) (actual
time=738.614..738.614 rows=1731436 loops=1)
                         Index Cond: (denied_pay IS NULL)
                   ->  Bitmap Index Scan on claims_document_type
(cost=0.00..34839.40 rows=1885724 width=0) (actual
time=852.203..852.203 rows=1886354 loops=1)
                         Index Cond: (document_type = 0)
                   ->  Bitmap Index Scan on claims_status
(cost=0.00..36743.62 rows=1988686 width=0) (actual
time=603.890..603.890 rows=1991651 loops=1)
                         Index Cond: (status >= 0)
                   ->  Bitmap Index Scan on claims_group_plan_id
(cost=0.00..38711.90 rows=1845543 width=0) (actual
time=444.953..444.953 rows=1922062 loops=1)
                         Index Cond: ((group_plan_id IS NOT NULL) AND
(group_plan_id > 0))
             SubPlan 1
               ->  Index Scan using claim_attachments_claim on
claim_attachments ca  (cost=0.00..10241.71 rows=2 width=0) (actual
time=17.884..17.884 rows=0 loops=1741)
                     Index Cond: (claim_id = clm.id)
             SubPlan 2
               ->  Aggregate  (cost=10241.72..10241.73 rows=1
width=0) (actual time=18.062..18.063 rows=1 loops=3696)
                     ->  Index Scan using claim_attachments_claim on
claim_attachments ca  (cost=0.00..10241.71 rows=2 width=0) (actual
time=14.872..18.053 rows=0 loops=3696)
                           Index Cond: (claim_id = clm.id)
       ->  Index Scan using claim_entries_claim_id on claim_entries
ce  (cost=0.00..9.41 rows=1 width=4) (actual time=3.081..3.081 rows=0
loops=145)
             Index Cond: (clm.id = claim_id)
             Filter: ("left"((cpt_code)::text, 1) = '8'::text)
Total runtime: 144707.873 ms