Insufficient storage error even after partition upgrade for FP1

[Pulling this over here from the other thread, see link “Unable to install some apps…”]
Couldn’t wait. I did a hard reset this morning, without doing a cache wipe. Still, what @Hugo_Buddelmeijer says is right:

I can confirm that: after the reset, GApps are installed. However, I specifically uninstalled Google Search yesterday and tried (unsucsessfully) to reinstall it from the app store. Now, it is gone.

I restored all my personal info and the apps from a backup, this time the standard out-of-the-box “Backup and Restore” app. This did not, however, re-install/restore all apps! For example, Twidere and TextSecure were there (but the credentials and data were gone). Threema, e.g., was not. Some other paid apps weren’t there, as well.

I opend Titanium Backup (Pro), which then prompted for Super User rights, and asked if I wanted ro restore my android ID. Which I did.

I did restore some apps and their data from Titanium Backup, like Twidere, and TextSecure. As Hugo says:

Worked fine. I actually also tried and restored the clock app, including alarms (it’s a system app). Worked as well. But I kept away from restoring most system apps.

Now, something funny: I checked the the PlayStore for updates, and could update the (restored) Oeffi Transport Buddy to the newest version - which somehow behaved like a new installation, placing a icon for the app on the home screen.
However, some apps (some of them payed apps) are now not shown in the “Installed” apps tab in the PlayStore, but in the “All” apps tab. And I double-checked: it said I should pay, again.

I decided not to, but to restore some of them from the Titanium Backup. One by one. Which worked. However, they are still shown in the “All” apps tab. Now, however, the price is gone, instead it shows “Installed” next to the app name.

This is annoying, to say the least.