Titanium Backup: Describe error: There is a problem parsing the package
There is one issue not mentioned online. When you disable Google Play Store - you need to untick some setting under security. You need to tick Unknown sources and UN-TICK Verify apps - while Play Store is still installed and actively running.

At least this solved parsing issue for me without the need to do backups again. Somehow google has managed to block Titanium backup ...