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.