InnoDB Deadlock Error

Dear Friends,

I have an InnoDB deadlock error which is happening everyday nearly at the same time, below is the output of “SHOW ENGINE INNODB STATUS”:
{
*** (1) TRANSACTION:
TRANSACTION 354034E1, ACTIVE 0 sec starting index read
mysql tables in use 3, locked 3
LOCK WAIT 4 lock struct(s), heap size 1248, 3 row lock(s)
MySQL thread id 1793913, OS thread handle 0x7f0844a67700, query id 49373296 localhost db_user Searching rows for update
UPDATE orderlines SET current_status_id = 30, supplier_order_date = ‘2013-03-15’ WHERE order_file_id = 109782 AND current_status_id = 31
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 16052 page no 190470 n bits 1232 index orderlines_FKIndex2 of table db.orderlines trx id 354034E1 lock_mode X waiting
*** (2) TRANSACTION:
TRANSACTION 354034DE, ACTIVE 0 sec fetching rows, thread declared inside InnoDB 225
mysql tables in use 3, locked 3
463 lock struct(s), heap size 47544, 1419 row lock(s)
MySQL thread id 1793915, OS thread handle 0x7f08455d4700, query id 49373289 localhost db_user Searching rows for update
UPDATE orderlines SET current_status_id = 30, supplier_order_date = ‘2013-03-15’ WHERE order_file_id = 109780 AND current_status_id = 31
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 16052 page no 190470 n bits 1232 index orderlines_FKIndex2 of table db.orderlines trx id 354034DE lock_mode X
*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 16052 page no 168029 n bits 104 index PRIMARY of table db.orderlines trx id 354034DE lock_mode X locks rec but not gap waiting
*** WE ROLL BACK TRANSACTION (1)
}

And the following is the two tables structure which related to the deadlock:

CREATE TABLE orderlines (
orderline_id int(10) unsigned NOT NULL AUTO_INCREMENT,
current_status_id int(10) unsigned NOT NULL,
order_id bigint(20) NOT NULL,
order_file_id int(10) DEFAULT NULL,
supplier_order_date date DEFAULT NULL,
PRIMARY KEY (orderline_id),
KEY orderlines_FKIndex1 (order_id),
KEY orderlines_FKIndex2 (current_status_id),
KEY orderlines_FKIndex5 (order_file_id),
CONSTRAINT orderlines_ibfk_161 FOREIGN KEY (order_id) REFERENCES orders (order_id) ON DELETE CASCADE ON UPDATE CASCADE,
CONSTRAINT orderlines_ibfk_171 FOREIGN KEY (order_file_id) REFERENCES supplier_order (order_file_id) ON DELETE SET NULL ON UPDATE CASCADE,
CONSTRAINT orderlines_ibfk_91 FOREIGN KEY (current_status_id) REFERENCES lkp_orderline_status (status_id) ON DELETE NO ACTION ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

CREATE TABLE lkp_orderline_status (
status_id int(11) unsigned NOT NULL,
status_name varchar(255) CHARACTER SET latin1 NOT NULL,
status_table varchar(255) CHARACTER SET latin1 NOT NULL,
PRIMARY KEY (status_id),
KEY status_name (status_name)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

My problem is that I was not facing that error until I migrate the DB server to another strong one with new MySQL version.

The old MySQL version info:

Variable_name Value
innodb_version 1.1.7-20.1
version 5.5.13-55-log
version_comment Percona Server (GPL), Release rel20.4, Revision 138
version_compile_machine x86_64
version_compile_os Linux

The new MySQL version info:

Variable_name Value
innodb_version 1.1.8-rel29.3
version 5.5.28-29.3-log
version_comment Percona Server (GPL), Release rel29.3, Revision 388
version_compile_machine x86_64
version_compile_os Linux

My question is: Why the deadlock error is always happening after the upgrade process? and how can I fix it?
Any suggestions will be appreciated …

Thank,