Planner regression in 8.0.x ?

Last night I upgraded my three DB servers from 7.4.8 to 8.0.4 (RPM from
the PostgreSQL site).  This morning I found my servers very busy from
three queries that were two hours old:

The following query ran in a fraction of a second on 7.4.8:

SELECT receipt_date, process_date, callsign AS applicant_callsign,
operator_class, geo_region, uls_file_num,
   vanity_callsign, prediction, predict_level AS _level, licensee_id AS
_lid,
   operator_group AS _oper_group, vanity_group AS _vanity_group,
vanity_region AS _vanity_region, usps AS _usps, end_date AS _end_date,
   (SELECT TRUE  FROM archivejb  WHERE (   (callsign = gen.callsign  AND
license_status = 'A'  AND prev_callsign = gen.vanity_callsign)
                                        OR (callsign =
gen.vanity_callsign                     AND licensee_id   =
gen.licensee_id))
                                   AND grant_date < receipt_date  LIMIT
1) AS _verified,
   (SELECT TRUE  FROM "ReservedCall"  WHERE vanity_callsign ~ pattern
LIMIT 1) AS _reserved, radio_service AS _service
 FROM genapp_pending_ AS gen  WHERE vanity_type::CHAR = 'A'
 ORDER BY receipt_date DESC, SUBSTRING( callsign, '[0-9]' ), callsign,
uls_file_num DESC, seq_num

On 8.0.4, it runs for hours (stopped after two hours).  Here's the plan:

 Sort  (cost=921303.61..921303.61 rows=2 width=114)
   Sort Key: "_Pending".receipt_date,
"substring"(("_Pending".callsign)::text, '[0-9]'::text),
"_Pending".callsign, "_Pending".uls_file_num, "_Pending".seq_num
   ->  Nested Loop  (cost=0.00..921303.60 rows=2 width=114)
         Join Filter: (("outer".prediction)::text ~~
("inner".prediction)::text)
         ->  Seq Scan on "_Pending"  (cost=0.00..2266.61 rows=10 width=112)
               Filter: ((((((vanity_type)::text || ' - '::text) ||
(COALESCE((subplan), '???'::character
varying))::text))::bpchar)::character(1) = 'A'::bpchar)
               SubPlan
                 ->  Limit  (cost=0.00..1.07 rows=1 width=19)
                       ->  Seq Scan on "_VanityType"  (cost=0.00..1.07
rows=1 width=19)
                             Filter: (vanity_id = $8)
         ->  Seq Scan on "_Prediction"  (cost=0.00..1.21 rows=21 width=18)
         SubPlan
           ->  Index Scan using "_HD_pkey" on "_HD"  (cost=0.00..3.01
rows=1 width=6)
                 Index Cond: (unique_system_identifier = $7)
           ->  Limit  (cost=0.00..1.01 rows=1 width=0)
                 ->  Seq Scan on "_ReservedCall"  (cost=0.00..1.01
rows=1 width=0)
                       Filter: ($2 ~ (pattern)::text)
           ->  Limit  (cost=455905.32..459495.68 rows=1 width=0)
                 ->  Subquery Scan archivejb  (cost=455905.32..498989.60
rows=12 width=0)
                       Filter: (((callsign = $4) AND (license_status =
'A'::bpchar) AND (prev_callsign = $2)) OR ((callsign = $2) AND
(licensee_id = $5)))
                       ->  Unique  (cost=455905.32..488509.64
rows=465776 width=229)
                             ->  Sort  (cost=455905.32..457069.76
rows=465776 width=229)
                                   Sort Key: callsign, fcc_reg_num,
licensee_id, prev_callsign, trustee_callsign, applicant_type,
operator_class, prev_class, radio_service, license_status, geo_region,
grant_date, effective_date, cancel_date, expire_date, last_action_date,
entity_name, first_name, middle_init, last_name, name_suffix, address,
po_box, city, state, zip9, sys_id
                                   ->  Append  (cost=0.00..194809.19
rows=465776 width=229)
                                         ->  Subquery Scan "*SELECT* 1"
(cost=0.00..75019.36 rows=1 width=229)
                                               ->  Nested Loop
(cost=0.00..75019.35 rows=1 width=229)
                                                     Join Filter:
("outer".callsign = "inner".callsign)
                                                     ->  Merge Join
(cost=0.00..75013.39 rows=1 width=216)
                                                           Merge Cond:
("outer".unique_system_identifier = "inner".unique_system_identifier)
                                                           Join Filter:
("outer".callsign = "inner".callsign)
                                                           ->  Index
Scan using "_EN_pkey" on "_EN"  (cost=0.00..37158.11 rows=911646 width=158)
                                                           ->  Index
Scan using "_AM_pkey" on "_AM"  (cost=0.00..21972.80 rows=906891 width=58)
                                                     ->  Index Scan
using "_HD_pkey" on "_HD"  (cost=0.00..5.91 rows=1 width=49)
                                                           Index Cond:
("outer".unique_system_identifier = "_HD".unique_system_identifier)
                                                           Filter:
(grant_date < $6)
                                         ->  Subquery Scan "*SELECT* 2"
(cost=0.00..119789.84 rows=465775 width=186)
                                               ->  Seq Scan on "_Lic"
(cost=0.00..115132.09 rows=465775 width=186)
                                                     Filter:
((COALESCE((grant_date)::timestamp without time zone, (expire_date - '10
years'::interval)))::date < $6)
           ->  Index Scan using "_HD_pkey" on "_HD"  (cost=0.00..5.91
rows=1 width=8)
                 Index Cond: (unique_system_identifier = $3)
           ->  Seq Scan on "_GeoRestrict"  (cost=0.00..1.20 rows=1 width=1)
                 Filter: ($2 ~ (pattern)::text)
           ->  Limit  (cost=0.00..1.05 rows=1 width=9)
                 ->  Seq Scan on "_CallsignGroup"  (cost=0.00..1.05
rows=1 width=9)
                       Filter: (group_id = $1)
           ->  Limit  (cost=0.00..2.17 rows=1 width=14)
                 ->  Nested Loop  (cost=0.00..2.17 rows=1 width=14)
                       Join Filter: ("inner".group_id = "outer".group_id)
                       ->  Seq Scan on "_OperatorClass"
(cost=0.00..1.07 rows=1 width=5)
                             Filter: (class_id = $0)
                       ->  Seq Scan on "_CallsignGroup"
(cost=0.00..1.04 rows=4 width=14)
           ->  Limit  (cost=0.00..1.07 rows=1 width=13)
                 ->  Seq Scan on "_OperatorClass"  (cost=0.00..1.07
rows=1 width=13)
                       Filter: (class_id = $0)

In the query, if I remove the "(SELECT TRUE FROM archivejb ... LIMIT 1)
AS _verified", the query runs in a fraction of a second.

"archivejb" is a UNION of one VIEW (JOIN of three tables, w/ 0.9 million
rows) and one TABLE (1.3 million rows).  All the other tables are tiny
(<100 rows).

If I can't fix this, I'll have to go back to 7.4.8.

HELP!

-- Dean