Any app that exhibits this behavior has been signed with a "generic" Android key, rather than an actual authority-issued key. Amazon, in their infinite wisdom, has also signed a few system apps with these keys. In order to correct the issue, part of the upgrade process to 7.2.3 involves replacing the cached keys with real ones (whereas the correct correction would be to re-sign the apps correctly.
Kinology, at boot time, runs the script to do this key replacement nonsense so that certain system apps will actually work (Unified Search, for example). Unfortunately, the side effect of this is that non-system apps that happen to be signed with generic keys also get this treatment. Unfortunately again, non-system apps that have their keys changed unexpectedly in this manner are denied exec access (basic Android security).
Personally, I would not trust any app that is signed with a generic key. However, I will continue to look for a solution to the key issue that doesn't have this particular consequence. No promises at this time, though....