Both your query plans end with this nested loop join which is taking up about half your time in your query. Notice the estimation of the result set is off by a factor of about 10 here, which means a nested loop might be not so good a choice for this. Try increasing default stats target and re-analyzing to see if that helps. 1000 is the max you can give that a shot right off to see if it helps. If it does, drop it until the numbers start to go off again and stop.
For a quicker test, you can set enable_nestloop = off in the psql command line and then run the query by hand and see if that helps.Thanks - the nested loop is indeed causing problems - reducing seq_page_cost had the same effect of removing the nested loop for this query. We'd noticed the poor row count estimation. Increasing the statistics doesn't seem to have much effect, but we'll have more of a go with it.
