Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES], on only one device, Samsung S3 w/4.3

Any idea? We’ve got a number of different Android devices here, but only that one device is having this issue, using Unity 4.3.3, Android 4.3. I read that someone else had that issue, ignored it, and then their build on the store didn’t work for a certain amount of devices; we really want to avoid that.

Needed to update our Android SDK