Really slow UPDATE and DELETE

I have a set of tables, of which products is one:

Table "products"
Attribute | Type | Modifier
--------------------+------------------------+---------------------------------------------------
id | integer | not null default nextval('seq_Products_ID'::text)
fk_company_id | numeric(6,0) |
fk_label_id | numeric(6,0) |
fk_formats_id | numeric(3,0) |
fk_descriptions_id | integer |
fk_genre_id | numeric(2,0) |
fk_variant_id | numeric(2,0) |
release | date |
title | character varying(200) |
isbn | isbn |
artist | character varying(200) | default '\'Unknown Artist\''
tagline | character varying(300) |
blurb | text |
image | oid |
mediacount | numeric(2,0) | default '1'
Indices: idx_products_fk_formats_id,
idx_products_fk_variant_id,
idx_products_lower_artist,
idx_products_lower_title,
idx_products_oid,
products_pkey
Constraint: (title <> ''::"varchar")

Those fk_*s are foreign keys to other tables.
Inserts and selects on this table are really fast with indexes, and
pretty fast without. This machine has over a GB ram, and I've put
sort_mem = 131072
shared_buffers = 65536
fsync = false
into the config. Postgres has been seen to eat over 600MB ram, but the
machine hasn't touched swap yet at all.

In case the vacuum has some useful info:

depos=# vacuum verbose products;
NOTICE: --Relation products--
NOTICE: Pages 4856: Changed 2, reaped 10, Empty 0, New 0; Tup 342366: Vac 49, Keep/VTL 0/0, Crash 0, UnUsed 39, MinLen 63, MaxLen 155; Re-using: Free/Avail. Space 6400/6240; EndEmpty/Avail. Pages 0/2. CPU 0.03s/0.06u sec.
NOTICE: Index products_pkey: Pages 1449; Tuples 342366: Deleted 49. CPU 0.01s/0.43u sec.
NOTICE: Index idx_products_lower_title: Pages 1704; Tuples 342366: Deleted 49. CPU 0.02s/0.47u sec.
NOTICE: Index idx_products_lower_artist: Pages 1369; Tuples 342366: Deleted 49. CPU 0.00s/0.47u sec.
NOTICE: Index idx_products_fk_formats_id: Pages 754; Tuples 342366: Deleted 49. CPU 0.00s/0.43u sec.
NOTICE: Index idx_products_fk_variant_id: Pages 753; Tuples 342366: Deleted 49. CPU 0.00s/0.44u sec.
NOTICE: Index idx_products_oid: Pages 754; Tuples 342366: Deleted 49. CPU 0.00s/0.43u sec.
NOTICE: Rel products: Pages: 4856 --> 4855; Tuple(s) moved: 47. CPU 0.00s/0.02u sec.
NOTICE: Index products_pkey: Pages 1449; Tuples 342366: Deleted 47. CPU 0.00s/0.37u sec.
NOTICE: Index idx_products_lower_title: Pages 1704; Tuples 342366: Deleted 47. CPU 0.00s/0.39u sec.
NOTICE: Index idx_products_lower_artist: Pages 1369; Tuples 342366: Deleted 47. CPU 0.00s/0.39u sec.
NOTICE: Index idx_products_fk_formats_id: Pages 754; Tuples 342366: Deleted 47. CPU 0.00s/0.36u sec.
NOTICE: Index idx_products_fk_variant_id: Pages 753; Tuples 342366: Deleted 47. CPU 0.00s/0.37u sec.
NOTICE: Index idx_products_oid: Pages 754; Tuples 342366: Deleted 47. CPU 0.00s/0.37u sec.
NOTICE: --Relation pg_toast_3818171--
NOTICE: Pages 0: Changed 0, reaped 0, Empty 0, New 0; Tup 0: Vac 0, Keep/VTL 0/0, Crash 0, UnUsed 0, MinLen 0, MaxLen 0; Re-using: Free/Avail. Space 0/0; EndEmpty/Avail. Pages 0/0. CPU 0.00s/0.00u sec.
NOTICE: Index pg_toast_3818171_idx: Pages 1; Tuples 0. CPU 0.00s/0.00u sec.
VACUUM

The problem I'm having is that UPDATES and DELETEs are really, really
slow. For example,
UPDATE products SET release = '1994/10/01' WHERE id = '73';
takes over 20 seconds. I've tried removing all indexes apart from the
one on id; because I can see that is used:

depos=# explain UPDATE products SET release = '1994/10/01' WHERE id = '73';
NOTICE: QUERY PLAN:

Index Scan using products_pkey on products (cost=0.00..4.60 rows=1 width=154)

What can I do to make UPDATES fast enough ? I need really to be able
to do at least 2 a second.

Thanks,

Nick

--
Part 3 MEng Cybernetics; Reading, UK http://www.nickpiper.co.uk/
Change PGP actions of mailer or fetch key see website 1024D/3ED8B27F
Choose life. Be Vegan :-) Please reduce needless cruelty + suffering !