8.1 -> 8.4 regression

(Apologies if this ends up coming through multiple times - my first attempts seem to have gotten stuck.)

We recently took the much needed step in moving from 8.1.19 to 8.4.2. We took the downtime opportunity to also massively upgrade our hardware. Overall, this has been the major improvement you would expect, but there is at least one query which has degraded in performance quite a bit. Here is the plan on 8.4.2:
http://wood.silentmedia.com/bench/842

Here is the very much less compact plan for the same query on 8.1.19:
http://wood.silentmedia.com/bench/8119

I think the problem might be that 8.1.19 likes to use a few indexes which 8.4.2 doesn't seem to think would be worthwhile. Perhaps that's because on the new hardware almost everything fits into ram, but even so, it would be better if those indexes were used. The other differences I can think of are random_page_cost (2 on the new hardware vs. 2.5 on the old), a ten-fold increase in effective_cache_size, doubling work_mem from 8MB to 16MB, and that we analyze up to 100 samples per attribute on 8.4.2, while our 8.1.19 install does 10 at most. Still, the estimates for both plans seem fairly accurate, at least where there are differences in which indexes are getting used.

Everything has been analyzed recently, and given that 8.4.2 already has 10x more analysis samples than 8.1.19, I'm not sure what to do to coax it towards using those indexes.