Надо смотреть следующие вещи:
1. Логи приложения на устройстве. Вы можете их посмотреть с помощью утилиты а-ля
https://play.google.com/store/apps/details?id=com.... по крайней мере у меня на старом ведре Sony Z1 оно работает без рута (кто-то в комментах к вашему вопросу писал о том, что логкэты могут требовать рут прав, этот точно не требует для многих версий андроида). Также, для просмотра логов хватит просто установленного SDK с пакетом сопутствующих утилит на ноуте, к примеру (android sdk tools, ну сколько они занимают, мегабайтов 200 максимум).
2. Надо смотреть Ваш манифест. Там есть ряд нюансов, на которые может смотреть установщик apk android. Сходу не могу сказать, какие именно нюансы, просто надо документацию почитать.
3. Если вы используете нативные библиотеки, с некоторой долей вероятности Вы пытаетесь запустить приложение с библиотекой, скомпилированной для другой архитектуры.
4. Вы можете использовать в своем приложении устаревшие или наоборот, еще не существующие API для конкретной версии.
5. Если используете multi dex, у меня лично с ним был косяк для одного проекта, не запускался на 5-ке на некоторых устройствах. Плюнул, так как проект влезал в 64K ограничение на методы.
6. Если качаете приложение с флешки, к примеру, через адаптер, или еще как-то без проверки контрольных сумм, могут быть ошибки, связанные с битым файлом apk.
7. Приложение может не пропускать, к примеру, антивирус на устройстве. Может стоять запрет на установку приложений из сторонних источников. Может быть так, что существует запрет на установку apk фалов, не подписанных вовсе, или подписанных только debug ключами при отсутствии включенного режима разработчика (гипотеза).
С Вашей проблемой не сталкивался, накидал гипотетических вариантов.
