(Even) More on Weird index problem

Hey,
More info on the index problem.
I fixed the previous problem by doing a pg_upgrade and all that stuff.
Now explain actually says it's using indices and whatnot.
But now I'm having a different but related problem.

Now, If I do a select on one field, everything is all good and indices are
being used.  But, if I try to add a "OR" in there, even on the same field,
explain says indices are being used, but query is taking forever 5min+

With the query below, if I take out either one of the statements in the
(stmt OR Stmt) it returns immediately.  Top one returns 11 rows and
bottom one 20 rows.

The weird thing is, why is explain showing such a high cost for going
through the indices?

Both tables have been vacuumed(both normal and with analyze), so the
optimizer has completely up-to-date stats.

Thanks,
Ole Gjerde

Query with problem:
SELECT  AV_Parts.PartNumber,
        inventorysuppliers.companyname
 FROM inventorysuppliers,
      AV_Parts
   WHERE (inventorysuppliers.id = AV_Parts.VendorID) AND
         (
          (AV_Parts.RawPartNumber LIKE '6890040%')  OR
          (AV_Parts.RawPartNumber LIKE '123456%')
         );

explain output of query above:
NOTICE:  QUERY PLAN:

Nested Loop  (cost=183613.27 rows=12 width=32)
  ->  Index Scan using av_parts_rawpartnumber_index,
av_parts_rawpartnumber_index on av_parts  (cost=183609.17 rows=2 width=16)
  ->  Index Scan using inventorysuppliers_id_index on inventorysuppliers
(cost=2.05 rows=210 width=16)

EXPLAIN