MySQL's query plan is odd at times. What does an explain look like on that query? If any portion of the query, including subselects isn't able to use an index, it will report it. You can try to force indicies with USE INDEX/FORCE INDEX which can sometimes help.
Ah, I was having trouble with another slow query; however, the EXPLAIN showed that the correct indices were used. I managed to speed it up by restricting the size of the inner SELECT with some extra constraints. From 4 seconds downto 0.1 seconds!