Man, you've hit something here ...
The execution plan my installation's using is very similar, if not identical, to the last one you've posted that runs in 1MS on your machine (my eyes cross whenever I try to verify it's actually identical :)
How much buffer space do you have allocated? (-B from the postmaster command line or set in your PG startup control file)
I'm wondering if you might not be disk thrashing? That index scan does seem to be where the time is being spent, looking at your original explain with timing info.
Then again it may just be the fact that you've materialized the view.
Very strange ...
I think the view can be rewritten using "not exists" and that seems to generate a slightly nicer plan than the one above but I need to test to make sure my rewrite is actually equivalent ...
