deleting rows with foreign keys

Here's my table:

Table "public.tokens"
Column | Type |
Modifiers
-----------+-----------------------------
+------------------------------------------------------------
token_idx | bigint | not null default nextval
('tokens_token_idx_seq'::regclass)
token | character varying(140) | not null
last_seen | timestamp without time zone | default now()
Indexes:
"tokens_pkey" PRIMARY KEY, btree (token_idx)
"tokens_token_key" UNIQUE, btree (token)

I have ~250K rows in this table.
the token_idx is referenced in two other tables, both of whom have a
foreign key constraint to ON DELETE CASCADE.
Of the other two tables, one has ~1M rows and the other ~350K rows.
So they are both one to many relationships with many of the token
table rows appearing in the other two.

Problem:
Deleting one row can take 2 seconds.

Is there something I can do to improve the speed. Locking the tables
is an option as this is a maintenance procedure and not regular
business. But I don't know that this will be useful or practical.