Application not installed (different)
I finally figured out how to fix this.

What I did


I did a double factory reset: Nothing happened.
Downgraded to Android 4.2.2: Nothing happened.
Downgraded to Android 4.1.2: Nothing happened.
Upgraded to Android 4.3: Nothing happened.
Factory Reset: Gallery appeared!
Upgraded to Android 4.4.2: Gallery didn't disappear!