Very slow DELETE on 4000 rows of 55000 row table

I've got a DELETE FROM that seems to run forever, pegging the CPU at
100%. I can't figure out why it's slow. Any clues?

stage=# EXPLAIN DELETE FROM EG_INVOICE WHERE PERIOD_ID = 1017506;
Index Scan using ix22f7bc70c7de2059 on eg_invoice (cost=0.00..105.39
rows=3955 width=6)
Index Cond: (period_id = 1017506)

stage=# select count(*) FROM EG_INVOICE;
55376

stage=# select count(*) FROM EG_INVOICE where PERIOD_ID = 1017506;;
4603

stage=# \d EG_INVOICE;
Table "public.eg_invoice"
Column | Type | Modifiers
----------------+------------------------+-----------
invoice_id | integer | not null
cso_id | integer | not null
period_id | integer | not null
invoice_number | character varying(192) |
invoice_date | date |
plan_name | character varying(128) |
invoice_style | integer | not null
account_id | integer |
Indexes:
"eg_invoice_pkey" PRIMARY KEY, btree (invoice_id)
"invoice_number_idx" btree (invoice_number)
"ix22f7bc70c7de2059" btree (period_id)
Foreign-key constraints:
"fk22f7bc70c7de2059" FOREIGN KEY (period_id) REFERENCES
eg_billing_period(period_id)
"invoice_to_account" FOREIGN KEY (account_id) REFERENCES
eg_account(account_id)
"invoice_to_cso" FOREIGN KEY (cso_id) REFERENCES eg_cso(cso_id)

stage=# vacuum analyze verbose EG_INVOICE;
...
INFO: "eg_invoice": scanned 584 of 584 pages, containing 55376 live
rows and 0 dead rows; 3000 rows in sample, 55376 estimated total rows

PostgreSQL 8.1.8 on i686-redhat-linux-gnu, compiled by GCC gcc (GCC)
4.1.1 20070105 (Red Hat 4.1.1-51)

--
----
Visit http://www.obviously.com/