It seems indeed to be related to specific kind of apps. After searching for ‘Unlock Key’, none of the apps I tried (“Wi-Fi Rabbit Unlock Key” and “AppSwipe! Unlock Key”) work. (I don’t know the apps they unlock.) However, it’s not just paid apps, since most paid apps install without problems but Blendle is free and won’t install. “Scribblenauts Remix” is a normal paid app that won’t install (that is, not an ‘unlock’ app).
Edit: It seems that all apps which require Android 4.1 or higher won’t install, e.g. ‘Blendle’, ‘Scribblenauts’. Couldn’t find any other apps that require Android 4.1 or higher. 4.0 apps (‘Hungry Shark Evolution’) install fine. The ‘unlock’ apps do not require 4.1 though, but that might be device dependent. 4.1 introduced apk encryption, so that might indeed be related.