На ум приходят две вещи:
Убедитесь, что вы можете установить из других мест, кроме рынка. Перейдите в Настройки-> Приложения и установите флажок «Неизвестные источники».
Установка завершится неудачно, если у вас уже установлено приложение с другой подписью. Вручную удалите приложение на своем телефоне.
Редактировать: Кроме того, apk подписан с ключом релиза? Если это так, вы можете убедиться, что подписывание / выравнивание пакетов выполнено правильно.