Error: "Cannot add app " on Android When Trying to Add App from XenMobile App Store

The user gets "Cannot add app " on the Android device when trying to add an app from XenMobile App Store, and MDMERRORUSERDEPROVISIONED gets logged in Debug logs. Other already installed apps work normally. Device has not been purposefully removed, and the device looks normal in XenMobile console...