Данная ошибка возникла с приложение OneDrive.
Нашел Fix:
1) Качаем ADB
2) Включаем на телефоне режим отладки
2.1) Подключаем телефон по USB к ПК
3) Качаем apk приложения, которое не устанавливается
4) пытаемся установить: C:\adb>adb install onedrive.apk
Видим ошибку Failure [INSTALL_FAILED_DUPLICATE_PERMISSION perm=com.microsoft.skydrive.permiss
ion.C2D_MESSAGE pkg=com.microsoft.skydrive]

5) удаляем приложение: adb uninstall com.microsoft.skydrive
6) устанавливаем приложение из apk: adb install onedrive.apk