Все зависит от review team на которую попадете. У меня было много случаев, когда просили поменять. И в то же время в App Store куча приложений с одинаковыми иконками, причем от разных разработчиков, что говорит о том, что кто-то из них примитивный вор. И тем не менее это иногда пролазит. Если принципиально нужна именно эта иконка и не хотите рисковать, совет такой - уберите из продажи старое приложение, перед отправкой нового. А после одобрения, открывайте доступ к старому обратно. У меня это гарантировано прокатывало! Про Google Play не знаю...