MySQL InnoDB issue not using indexes correctly [Percona 5.6]

Question

I just installed Percona 5.6 on my new CentOS 6.4 server. It's a fast machine 32 core xenon, 72GB ram, 8x SAS RAID 10 setup. So far so good

My old server is a bit less powerful, and was running MySQL 5.1 still. So this was quite an upgrade. But I'm having some issues with InnoDB, it is not using the indexes correctly on some tables it seems. Where on my old machine the same queries were running fine.

Both servers have the same database. I did a mysqldump on the old machine and imported it onto the new Percona 5.6 server. Indexes stayed the same. Both servers use the same my.cnf config settings.

Table items has indexes on: item_id, item_format, item_private and contains about 40 million rows. Table formats has index on: format_id and contains about 250 rows.

SELECT 
i.item_name, i.item_key, i.item_date, f.format_long
FROM
items i, formats f
WHERE 
i.item_format = f.format_id
AND
i.item_private = 0 
ORDER BY 
i.item_id DESC LIMIT 8

On my old server this query takes about 0.0003 seconds. On the new server it takes over 100 seconds.

Query with EXPLAIN on OLD server.

+----+-------------+-------+--------+---------------+---------+---------+----------------------+------+-------------+
| id | select_type | table |  type  | possible_keys |   key   | key_len |         ref          | rows |    Extra    |
+----+-------------+-------+--------+---------------+---------+---------+----------------------+------+-------------+
|  1 | SIMPLE      | i     | index  | item_format   | PRIMARY |       4 | NULL                 |    8 | Using where |
|  1 | SIMPLE      | f     | eq_ref | PRIMARY       | PRIMARY |       4 | dbname.i.item_format |    1 |             |
+----+-------------+-------+--------+---------------+---------+---------+----------------------+------+-------------+

Query with EXPLAIN on NEW [problem] server.

+----+-------------+-------+------+---------------+-------------+---------+--------------------+------+---------------------------------+
| id | select_type | table | type | possible_keys |     key     | key_len |        ref         | rows |              Extra              |
+----+-------------+-------+------+---------------+-------------+---------+--------------------+------+---------------------------------+
|  1 | SIMPLE      | f     | ALL  | PRIMARY       | NULL        | NULL    | NULL               |  219 | Using temporary; Using filesort |
|  1 | SIMPLE      | i     | ref  | item_format   | item_format | 4       | dbname.f.format_id | 3026 | Using where                     |
+----+-------------+-------+------+---------------+-------------+---------+--------------------+------+---------------------------------+

You can see that it's using temporary and filesort. This seems to be the reason for the slowness.

Any idea how I could resolve this issue?