Probably you missed checking the "Normal apps (apk)" option
In order for the backup to properly be restored after OS upgrade/update, you would need to have the apk files. The apk files are backed up by Titanium Backup as apk.gz files ONLY if the Menu -> Preferences -> Normal apps (apk) is checked before you back up the apps. Otherwise, it would only backup the app properties and data and not the apk files.
So this is how it works:
Scenario 1: Menu -> Preferences -> Normal apps (apk) is checked
With Titanium Backup, you can restore the APP + DATA.
Scenario 2: Menu -> Preferences -> Normal apps (apk) is unchecked
With Titanium Backup, you can restore only the DATA, but you can do so only after you install the app either from playstore or manually (in case if you have the .apk file).
Hope this helps.