Я видел эту ошибку, когда на устройстве уже была копия приложения, подписанная с помощью ключа разблокировки. Вот что я рекомендую ...
- Сделайте чистую сборку вашего проекта
- Удалить приложение с телефона через менеджер приложений на телефоне
- Попробуйте запустить снова
Что-то еще, на что стоит обратить внимание, это где приложение установлено для установки. Если это SD-карта, убедитесь, что на виртуальной SD-карте достаточно места.