query stopped working after tables > 50000 records

Hi,
I have a query that does a left outer join. The query gets some text
from a reference table where one of the query's main tables may or may
not have the text's tables id. It wasn't super fast, but now it simply
won't execute. It won't complete either through odbc or via pgadmin
(haven't yet tried via psql). A week ago (with considerably fewer
records in the main table) it executed fine, not particularly quickly,
but not that slowly either. Now it locks up postgres completely (if
nothing else needs anything it takes 100% cpu), and even after an hour
gives me nothing. I have come up with a solution that gets the text via
another query (possibly even a better solution), but this seems very
strange.
Can anyone shed some light on the subject? I tried a full vacuum on the
tables that needed it, and a postgres restart, all to no avail.
Cheers
Antoine
ps. I can send the query if that will help...
pps. running a home-compiled 8.1.1 with tables in the query having 70000
records, 30000 records and 10 for the outer join. Without the left outer
join it runs in ~ 1 second.