What happened ?
Try to find more details about the table, once again and catch the scenario what and why it is getting LOCKED.
SHOW ENGINE INNODB STATUS\G;
SHOW FULL PROCESSLIST;
Why happened ?
If a transaction is happening on that particular table, then another transaction on the same will have to wait, as the first thread is holding a record lock on some record (row level locking).
For reference : http://dev.mysql.com/doc/refman/5.0/en/set-transaction.html

which means the second transaction will have to wait 50 seconds (default value) to obtain a LOCK.
Resolution steps :
As you said "All table columns are indexed properly". Still ensure that you have indexes on the foreign key constraints. Just put indexes on keys which will be used in WHERE condition & JOIN ON condition.
Consider to increase 'innodb_lock_wait_timeout' slightly and check again
set innodb_lock_wait_timeout=120 ;
By default in Innodb, database transaction isolation level would be 'REPEATABLE READ'.

Consider to change that to 'READ COMMITTED'.
mysql> SET tx_isolation = 'READ-COMMITTED';
mysql> SET GLOBAL tx_isolation = 'READ-COMMITTED';