The latest Google Play Services update has somehow broken major functionality in both Titanium Backup and Substratum. Titanium Backup has suddenly become stuck at zero percent while restoring, and Substratum simply fails to apply themes anymore. Both of these apps do require root, but they've slowly become essential to rooted users, especially since apps like these come into play when you're deciding what your next phone should be.
Titanium is practically the Swiss Army knife of application management. It's capable of backing up and restoring applications along with their data, as well as disabling and enabling apps, and it can change installation locations as well. Substratum is an extremely powerful theming engine, one that works on practically every AOSP-based ROM (including CyanogenMod and LineageOS), and is capable of theming every single app available on Android (of course, you'll need to find a developer willing to take on this mission or simply pick up theming yourself).
It seems as though Google is in the middle of increasing the security of their app verification systems, and the change has taken place on the server side, so downgrading your Google Play Services app won't fix these problems. Until the developers of Titanium Backup and Substratum find a way to get around Google's update themselves, there's a quick way to get both apps up and running again, as well as any other root applications which have suddenly begun acting up.
Fixing Titanium Backup and Substratum is a two-step process, but do note that we'll be disabling Google's built-in security features by doing so. Other than that, the fix is straightforward and relatively simple.
The first step is very simple—all we'll be doing is disabling Google's constant scanning. Not only will your root apps begin working correctly again, but you'll all see a significant decrease in app installation times.
Open up the Settings app and select the "Google" entry. From there, tap on "Security," then choose "Verify apps" on the following screen. Finally, uncheck the "Scan device for security threats," then move on to the next step.
For this step, you'll need to enable "Developer options" if you haven't already done so. With that taken care of, head to the Developer options menu near the bottom of your system Settings page, then disable the "Verify apps over USB" option, and you'll be all set to go.
Why this option has an effect on Titanium Backup and Substratum is yet to be figured out, but unchecking it will get the job done. Thankfully, Google didn't completely mess up Substratum and Titanium Backup, as they're both favorites in the rooting community and there simply aren't any apps that could replace them.
While both apps did break due to Google's increased security, this is a good sign—it shows that Google is trying to make Android safer. But it's a shame that it seems like they might be poking in the wrong direction, as these apps are certainly not security threats. A better start, in my opinion, would be detecting or preventing problematic apps that get uploaded to the Google Play Store.