DELETE running at snail-speed

I'm running a delete command on a postgresql-8.1.9 server. 25000
tuples are delete, time is ~ 400 secs

the command:
delete from downtime where start<'Aug 1 00:00:00 2008'

The table definitions are:
linie4=> \d downtime
Table "public.downtime"
Column | Type |
Modifiers
------------+-----------------------------
+---------------------------------------------------------------
downtimeid | integer | not null default nextval
('downtime_downtimeid_seq'::regclass)
status | smallint |
start | timestamp without time zone | default now()
machineid | smallint |
a_nr | integer |
Indexes:
"downtime_pkey" PRIMARY KEY, btree (downtimeid)
"idx_downtime_start" btree ("start")
Foreign-key constraints:
"machineid_ok" FOREIGN KEY (machineid) REFERENCES machine
(machineid) ON UPDATE CASCADE ON DELETE CASCADE

linie4=> \d downtime_detail
Table "public.downtime_detail"
Column | Type |
Modifiers
------------+----------
+--------------------------------------------------------------------
detailid | integer | not null default nextval
('downtime_detail_detailid_seq'::regclass)
downtimeid | integer |
detail | smallint |
Indexes:
"downtime_detail_pkey" PRIMARY KEY, btree (detailid)
Foreign-key constraints:
"statusid_ok" FOREIGN KEY (downtimeid) REFERENCES downtime
(downtimeid) ON UPDATE CASCADE ON DELETE CASCADE

I suspect the foreign key constraint of downtime_detail to slow down
the delete process. Is this a bug, probably fixed in latest version
(8.1.x) or should I drop the constraint and recreate after deletion -
which I only see as workaround ?

Gerhard