[AT&T Samsung Galaxy S 4 Themes and Apps] saurik:
Interesting. The only thing Substrate does to your device is add four symlinks: two of them are for Substrate-specific libraries in /system/lib (and so have nothing to do with anything else), and two of them are a liblog.so injection mechanism. These latter two involve one file /vendor/lib/liblog!.so (which is irrelevant due to the ! unless Substrate is doing something) and /vendor/lib/liblog.so, which is the only "active ingredient", as the other links were all meaningless.

The question, then, is whether when you deleted the APK if it also deleted the /data folder for Substrate. If so, then the linker would attempt to load /vendor/lib/liblog.so, fail as the file isn't found, and the system would continue exactly-as-stock. If it didn't, then it should have continued to fail just as hard as it otherwise would have, as nothing would have been changed. UNLESS you are actually describing an issue you had with WinterBoard, not Substrate... maybe people are equating them.

So, to verify: was your issue with Substrate itself, or with WinterBoard? If the issue was with WinterBoard (which is highly likely: WinterBoard with a theme that is fundamentally incompatible with your ROM /will/ cause your device to not boot up; this is not a bug: this is just how it would work) then you should have just held down volume-up and attempted to select another theme. (Alternatively, if WinterBoard was just fundamentally broken, uninstalled it.)

---------- Post added at 09:08 PM ---------- Previous post was at 09:02 PM ----------

With a bootloader unlock (allowing you to run a custom recovery), Substrate is harmless: it doesn't modify any of the files on your device, and so deleting what it does using an update.zip or just using adb in recovery takes a couple minutes. That said, it should definitely have worked on your device. To be clear: I tested it on a large number of devices, but it is really hard to test it on every single possible device, as there are so many :(.

The key issue seemed to be that Samsung made something of a mistake compiling their programs: they wanted access to property_get, which is in libcutils.so, but as that isn't in the NDK they seem to have wedged it into their liblog.so and then told their linker to not complain about missing symbols. The result is that they have programs on the device that require libcutils.so symbols to be exported from liblog.so, or they fail to run.

This issue was been fixed in later versions of Substrate, based on feedback from people testing on devices such as the S4. Additionally, Substrate now has features that allow it to detect these kinds of issues before they happen: it analyses the set of symbols exported by the copy of liblog.so on the device to make certain that it is not missing anything. (In a future build of Substrate, one could imagine it dynamically generating the injection.)

Regardless, I really am sorry you ran into that issue on the S4; as the bootloader isn't unlocked, if Substrate itself has something wrong with it (as opposed to one of the extensions you install), you get pretty screwed, as you can't just delete any of the files that form the injection. :(