Query runs a long time in some newer MySQL versions
Just off the bat, newer versions of MySQL actually improve innodb performance (especially 5.5). I would highly recommend updating to this version if you're going to run InnoDB.

One method you could use to hunt down why it's taking so much longer is using MySQL Profiles

mysql&gt; SET PROFILING=1;
mysql&gt; SHOW TABLES;
mysql&gt; SELECT * FROM foo;
mysql&gt; SET PROFILING=0;
Query OK, 0 rows affected (0.00 sec)

mysql&gt; SHOW PROFILES;
+----------+------------+-------------------+
| Query_ID | Duration   | Query             |
+----------+------------+-------------------+
|        1 | 0.09270400 | SHOW TABLES       |
|        2 | 0.00026400 | SELECT * FROM foo |
+----------+------------+-------------------+
2 rows in set (0.05 sec)

mysql&gt; SHOW PROFILE FOR QUERY 2;
+----------------------+----------+
| Status               | Duration |
+----------------------+----------+
| starting             | 0.000053 |
| checking permissions | 0.000009 |
| Opening tables       | 0.000032 |
| System lock          | 0.000010 |
| init                 | 0.000028 |
| optimizing           | 0.000003 |
| statistics           | 0.000012 |
| preparing            | 0.000008 |
| executing            | 0.000003 |
| Sending data         | 0.000068 |
| end                  | 0.000004 |
| query end            | 0.000007 |
| closing tables       | 0.000008 |
| freeing items        | 0.000013 |
| logging slow query   | 0.000003 |
| cleaning up          | 0.000003 |
+----------------------+----------+
16 rows in set (0.04 sec)


This should give you an indication of where it's hanging. From your explain output, you should try to get some indexing on the second and third tables instead of doing full table scans. But without DDL or the actual join columns, I can't suggest anything better than to research indexing strategies.