poor performance when recreating constraints on large tables

I originally posted this on admin, but it was suggested to post it to
performance so here goes -

I am in the process of implementing cascade on delete constraints
retroactively on rather large tables so I can cleanly remove deprecated
data. The problem is recreating some foreign key constraints on tables of
55 million rows+ was taking much longer than the maintenance window I had,
and now I am looking for tricks to speed up the process, hopefully there is
something obvious i am overlooking.

here is the sql I am running, sorry im trying to obfuscate object names a
little -

BEGIN;
ALTER TABLE ONLY t1 DROP CONSTRAINT fk_t1_t2_id;
ALTER TABLE ONLY t1 ADD CONSTRAINT fk_t1_t2_id FOREIGN KEY(id) REFERENCES
t2(id)
ON DELETE CASCADE
DEFERRABLE INITIALLY DEFERRED;
COMMIT;

t1 has 55 million rows
t2 has 72 million rows
the id columns are integer types
postgres version 8.3.8
there are nightly vacuum/analyze commands, and auto vacuum is enabled.

I have tried set constraints deferred, immediate, the id column on table 2
is indexed, its the primary key. Nothing really seems to impact the time it
takes to recreate the constraint. There may be memory settings to tweak, I
was able to get it to run on a faster test server with local storage in
about 10 minutes, but it was running for over an hour in our production
environment.. We took down the application and I verified it wasnt waiting
for an exclusive lock on the table or anything, it was running the alter
table command for that duration.

Let me know if there is anything else I can supply that will help the
review, thanks!

One additional question - is there any way to check how long postgres is
estimating an operation will take to complete while it is running?

Thanks again,
Mike