Nasty deadlock problem with RT 3.2.1

We have a RT 3.2.1 system that has been running well for about a week.
The database was upgraded from RT2 using the rt2-to-rt3 tools.

Last night we suddenly started getting errors like the following:

– Sep 30 09:21:34 rt3 RT: DBD::mysql::st execute failed: Deadlock found
when trying to get lock; Try restarting transaction at
/usr/lib/perl5/site_perl/5.8.3/DBIx/SearchBuilder/Handle.pm line 410.
(/opt/rt3/lib/RT.pm:250)
Sep 30 09:21:34 rt3 RT: RT::Handle=HASH(0xb62d7a0) couldn’t execute the
query ‘INSERT INTO Principals (ObjectId, PrincipalType, Disabled) VALUES
(?, ?, ?)’ at
/usr/lib/perl5/site_perl/5.8.3/DBIx/SearchBuilder/Handle.pm line 417.
(/opt/rt3/lib/RT.pm:250)
Sep 30 09:21:34 rt3 RT: Couldn’t create a Principal on new user create.
(/opt/rt3/lib/RT/User_Overlay.pm:224)
Sep 30 09:21:34 rt3 RT: Strange things are afoot at the circle K
(/opt/rt3/lib/RT/User_Overlay.pm:225)
Sep 30 09:21:34 rt3 RT: User creation failed in mailgateway: Could not
create user (/opt/rt3/lib/RT/Interface/Email.pm:225)
Sep 30 09:21:34 rt3 RT: Couldn’t load user ‘VNZCQWAUOP@msn.com’.giving
up (/opt/rt3/lib/RT/Interface/Email.pm:240)
Sep 30 09:21:34 rt3 RT: User ‘VNZCQWAUOP@msn.com’ could not be loaded
in the mail gateway (/opt/rt3/lib/RT/Interface/Email.pm:241)
Sep 30 09:21:34 rt3 RT: RT could not load a valid user, and RT’s
configuration does not allow for the creation of a new user for this
email (VNZCQWAUOP@msn.com). You might need to grant ‘Everyone’ the
right ‘CreateTicket’ for the queue TSREQ.
(/opt/rt3/lib/RT/Interface/Email.pm:530)
Sep 30 09:21:35 rt3 RT: RT could not load a valid user, and RT’s
configuration does not allow for the creation of a new user for your
email. (/opt/rt3/lib/RT/Interface/Email.pm:543)

The rights granted to Everyone are correct on this queue. I assume all
of this is stemming from the deadlock at the top? What can I do to
prevent this?

Thanks,
Brian