Poor performance problem with Materialize, 8.4 -> 9.1 (enable_material)

I'm upgrading from 8.4 to 9.1 and experiencing a performance degradation on
a key query with 2 views and 2 tables.

Old server "PostgreSQL 8.4.10 on i686-redhat-linux-gnu, compiled by GCC gcc
(GCC) 4.1.2 20080704 (Red Hat 4.1.2-51), 32-bit"
New server "PostgreSQL 9.1.4 on x86_64-unknown-linux-gnu, compiled by gcc
(GCC) 4.4.6 20110731 (Red Hat 4.4.6-3), 64-bit"

The query is as follows:
SELECT *
FROM edge_geom
WHERE (edge_geom.start_id, edge_geom.end_id) IN (('congo', 'donal'),
('golow', 'tundo'), ('golow', 'arthur'), ('golow', 'porto'), ('tundo',
'donal'), ('golow', 'newbo'), ('porto', 'donal'), ('decal', 'donal'),
('arthur', 'donal'), ('leandro', 'donal'), ('golow', 'decal'), ('golow',
'salad'), ('newbo', 'donal'), ('golow', 'congo'), ('salad', 'donal'),
('golow', 'leandro'));

Schema definitions:
http://pastebin.com/0YNG8jSC
I've tried to simplify the table and view definitions wherever possible.

And the query plans:
8.4: 314ms: http://explain.depesz.com/s/GkX
9.1: 10,059ms :http://explain.depesz.com/s/txn
9.1 with setting `enable_material = off`: 1,635ms
http://explain.depesz.com/s/gIu

So it looks like the Materialize in the query plan is causing the 30x
slowdown.
With the materialize strategy switched off , it's still 5x slower on 9.1
vs. 8.4.

Any help appreciated, I acknowledge that the tables and views aren't the
simplest.

Thanks!

Eoghan