InnoDB deadlocks

[vasiliy.gagin]

I'm experiencing deadlocks in MySQL InnoDB tables.
Here is significant information from SHOW INNODB STATUS:

*** (1) TRANSACTION:

TRANSACTION 0 328036006, ACTIVE 8 sec, process no 30377, OS thread id 2675510192 starting index read
mysql tables in use 1, locked 1
LOCK WAIT 2 lock struct(s), heap size 320
MySQL thread id 6729, query id 17905 qa02.qa.amientertainment.net 192.168.10.121 ami statistics

SELECT * from calliope_jukebox.jukeboxes where ... FOR UPDATE

*** (1) WAITING FOR THIS LOCK TO BE GRANTED:

RECORD LOCKS space id 0 page no 507908 n bits 104 index `PRIMARY` of table `calliope_jukebox/jukeboxes` trx id 0 328036006 lock_mode X locks rec but not gap waiting

Record lock, heap no 31 PHYSICAL RECORD: n_fields 53; 1-byte offs FALSE; info bits 0

*** (2) TRANSACTION:

TRANSACTION 0 328036002, ACTIVE 17 sec, process no 30377, OS thread id 2677316528 inserting, thread declared inside InnoDB 500
mysql tables in use 1, locked 1
7 lock struct(s), heap size 1024, undo log entries 2263
MySQL thread id 5961, query id 23135 qa02.qa.amientertainment.net 192.168.10.121 ami update

INSERT INTO calliope_jukebox.configured_songs SET ...

*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 0 page no 507908 n bits 104 index `PRIMARY` of table `calliope_jukebox/jukeboxes` trx id 0 328036002 lock_mode X locks rec but not gap
Record lock, heap no 31 PHYSICAL RECORD: n_fields 53; 1-byte offs FALSE; info bits 0

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 0 page no 507908 n bits 104 index `PRIMARY` of table `calliope_jukebox/jukeboxes` trx id 0 328036002 lock mode S waiting
Record lock, heap no 31 PHYSICAL RECORD: n_fields 53; 1-byte offs FALSE; info bits 0

*** WE ROLL BACK TRANSACTION (1)

All this statements are trying to lock same record from jukeboxes.

What I can tell looking to this is that:
1. Transction 2 INSERT into configured_songs tables has locked record (mode X) in jukeboxes table it referes to via FOREIGN KEY. And for some reason it trying to re-lock it in mode S??
2. Meanwhile transaction 1 SELECT FOR UPDATE from jukeboxes table is waiting to get lock (mode X too).

Somehow these transactions are managing to lock eachother. Though it seams that correct behaviour whould be for transaction 2 to get all locks it needs and for transaction 1 to keep waiting.

Can somebody shed the light on what lock modes X and S mean and on what is actually going on there. Is it bug or is it by design?
3. Then transction 2 INSERT trying to get lock