На сколько я помню, в случае зависимого подзапроса он будет выполняться каждый раз на каждую найденную запись основного запроса. Основной тоже тяжелый, mysql почему-то решил начинать разбор с таблицы px, видимо считает, что по ней получится самый эффективный фильтр, но непонятно тогда, почему предлагает использовать праймари индекс (кстати, какой он?), но не использует — недостаточная фильтрация?
Предлагаю попробовать избавиться от подзапроса в таком виде, провести analyze таблиц и посмотреть что выдаст explain в этом случае. Посмотрите сколько фактически записей остается по каждой таблице отдельно после применения нужных фильтров. Возможно оптимизатор ошибается в порядке выполнения запросов и нужно ему прямо указать в какой последовательности это нужно делать. Для меня тут загадка, почему он все-таки начинает с px и пробегает ее всю — примерно 4660 записей. В других таблицах больше что ли после фильтров?
Посмотрите параметры сервера, прогоните какой-нить утилиткой-тюнером, например mysqltuner.pl, поправьте всякие буферы. Еще возможно, что у вас до этого был сервер с нагретым кешем, а на инстансе чистый как стекло.