Text pattern JOINs that use indexes

I'm having a lot of trouble getting JOINs to work well with text
patterns.  I have a smallish table (4000 rows) containing prefixes that
I want to inner-join to a large table (500000 rows) of strings.  In
other words, I want to look up the few entries in the 500000 row table
which start with the strings in the 4000 row table.  PostgreSQL insists
on doing a sequential scan of the large table, even though it is
indexed on the field I'm using for the join.

Anyone got a solution?

Here are the "explains":

explain select * from files where name like 'foo%';
                                  QUERY PLAN
------------------------------------------------------------------------
-----
  Index Scan using files_name_key on files  (cost=0.00..6.01 rows=1
width=97)
    Index Cond: ((name >= 'foo'::text) AND (name < 'fop'::text))
    Filter: (name ~~ 'foo%'::text)


explain select * from test join files on files.name like test.filename
|| '%';
                              QUERY PLAN
---------------------------------------------------------------------
  Nested Loop  (cost=20.00..9450496.28 rows=1888140 width=129)
    Join Filter: ("outer".name ~~ ("inner".filename || '%'::text))
    ->  Seq Scan on files  (cost=0.00..9776.28 rows=377628 width=97)
    ->  Materialize  (cost=20.00..30.00 rows=1000 width=32)
          ->  Seq Scan on test  (cost=0.00..20.00 rows=1000 width=32)