Slow REST upload into large Gallery

I am loading images into a fairly large Gallery (currently 87k images) at http://search.designpatents.us

It seems the upload is causing at least two very slow queries for each image. Here is a look into the MySQL slow queries log:

# Time: 121126 0:57:24
# User@Host: user[user] @ localhost []
# Query_time: 10.498093 Lock_time: 0.000105 Rows_sent: 0 Rows_examined: 87445
SET timestamp=1353880644;
UPDATE `items`
SET `left_ptr` = `left_ptr` + 2
WHERE `left_ptr` >= '79';
# Time: 121126 0:57:39
# User@Host: user[user] @ localhost []
# Query_time: 15.420977 Lock_time: 0.000215 Rows_sent: 0 Rows_examined: 87445
SET timestamp=1353880659;
UPDATE `items`
SET `right_ptr` = `right_ptr` + 2
WHERE `right_ptr` >= '79';

Any ideas how to accelerate this?
I have played with various ideas to improve the mysql installation, but improvements have been marginal at best. Could shave a few seconds off one upload, but I am still at 30+ sec on average. Was a lot faster when I started moving to a new server a week ago...

Any ideas appreciated.