Index on a query with order
Try switching the index to be:

KEY `new_places_on_wishlist` (`wishlist_id`, `id`, `place_id`)


You are effectively doing the part of order by optimization manual that says it can't use the index because of ordering by non-consecutive parts of the key, although their example is different than your situation.

Basically you are currently doing

SELECT key_part2 FROM foo WHERE key_part1=constant ORDER BY key_part3