Does the postgresql.conf setting, default_statistics_target, have any effect on such large table scans? I remember for one client, changing from the default value to "500" seemed to make things better (you have to do an ANALYZE after changing the value).
