MySQL UPDATE Performance Issue I'm running out of ideas on a performance bottleneck I'm seeing on one of my projects.

The table in question is pretty small, with only 5396 records.  However, I'm seeing queries like this show up in our slow query log:

# Query_time: 17.482010  Lock_time: 0.000088  Rows_sent: 0  Rows_examined: 0
UPDATE `submissions` SET `updated_at` = '2011-11-15 20:12:44', `status` = 'eligible',   `published_at` = '2011-11-15 20:12:44' WHERE `submissions`.`id` = 5334


Submissions.id is the primary key.  

We are relatively read heavy, so we had query_cache enabled.  I've turned that off and it helped somewhat, but the updates still seem to be way too slow.

It only seems to effect this particular update, and the database overall has fairly light load with an average of 20 queries per second.

Any ideas on places to look would be greatly appreciated!

Clarifications

Mysql version: mysql  Ver 14.12 Distrib 5.0.51, for pc-linux-gnu (x86_64) using readline 5.2


Applications talking to the database are built with Ruby on Rails.  No explicit table locks.
What does EXPLAIN show for that query?  What does mysqltuner show? What does free -m show?

If turning the query cache off helped, I'd suspect you are running out memory and your machine is starting to swap.  Swapping is a pretty effective way to kill MySQL's performance.  The solution would be to either increase the memory of the machine, or tune MySQL to require less memory.