@humorkritik Thanks for the advice. I will try this as soon as I have a little more time. Even though it means to do the whole restoring process again. 
@Bobby Thanks, too. However, I’d like to have a more permanent solution rather than a work-around…
Hi @humorkritik!
Any updates on the “not enough space” situation? It became problematic for me, so if you still do not experience the same problem, I will factory reset my phone again.
Hi @dib0,
thanks for the reminder. 
I had no further “not enough space” problems after wiping, re-installing Titanium Backup pro, and restoring apps one by one (including only some system apps, like the notepad).
(Currently, my FP is partly defunct; got to send it back to have the service look at it. I wiped it, and will restore the same way like described above when I get it back from FP service.)
Lidwien, worked like a charm. Was wel even wat werk, maar ben weer een happy fairphone gebruiker! Willem
I had the same problem after upgrading to a unified storage partition. Clearing just the cache was unfortunately not a solution, so I did a factory reset following these instructions (including “wipe cache partition”). After that I used Titanium to restore my apps one by one, excluding all Google related apps. For me this solved the problem, although it took some time to fix it, I’m now very happy that I can enjoy the full storage capacity.
Hi all!
So this week my banking application stopped working and I couldn’t update. I decided now was the time to try this fix again. And it seems to have worked. Followed the description to the letter. Installed all apps individiually from the app store and restored the data for some of the apps with Titanium Backup (the first thing I did was install Titanium backup and restore the phone ID back the the previous one, and after that install the apps).
It looks like the problem is gone. So thanks all for the support and especially @humorkritik!
Glad to hear that!
Just FTR, personally, I didn’t go through the hassle of installing all apps from their respective sources (PlayStore, F-Droid etc.). I just installed TitaniumBackup, and restored the apps (in most cases: app + data) from the backup, one by one.
I finally had some time for a “factory reset” of my FP and (after xposed-framework, xprivacy, gravitybox, f-droid-store and f-droid-apps were installed) reinstalled every app via the GooglePlayStore (via their website because tapping on the phone for so long made me crazy). I then only restored the settings from the apps I really needed (I manually restored K9, Threema, TextSecure and after everything else the settings from xprivacy).
Since then everythings goes smooth, no more errors. What a relief… 
Hey guys, seems like the problem is not resolved yet, is it? I did most of the things mentioned above and nothing did work, due to some inadvertence I now lost most of my photos and data for the second time in two months. Due to some mistake backing up I am actually worse off now than before, because once installed apps which I installed since the last backup cannot be installed anymore after the partition upgrade…even though I usually arent bothered by some problems with the FP, this begins to start annoying me as well :-/
For my fairphone first edition it was indeed, as mentioned above, so that only 1 Gb of internal memory was available for apps. After deleting enough (in total 50 Mb) apps everithing works fine again. I was told that the system keeps a minimum of 100 Mb free, so if less is left no apps will be installed. Thanks everybody for helping me out.
In my case, it is.
Could you explain in a little more detail what steps you took, and what happens when you try to install the mentioned apps? I hope we can help you out, since my problems seem to be gone, and according to this thread, I’m not the only one who succeeded.
In a nutshell, what helped in my case was wiping everything and restoring non-system apps including their data one by one through TitaniumBackup. I also tried, in one case, re-installing an app from the PlayStore and restoring “data only” via TitaniumBackup. Worked as well, got a lot of content in there which would otherwise be gone.
The main reason behind insufficient storage is due to cache. You can view this page for resolving insufficient storage problem of android.
I tried to clear the situation with a little bit too enthusiastically playing the storage upgrade. Other than I thought initially, my last effective backup was from September, thus I lost some apps which I had installed in the meantime. The weird thing is that some apps can be installed through the Playstore (or amazon or f-droid doesnt make a difference) and others don’t, irregardless of whether they are 500kb or 25MB in size. Same applies for updates…I was able to update around 50% of my apps, others remain unupdated (some deliberatedly like FB, admittedly) because of insufficient storage space. But being not able to install new apps does affect me in the long run. True, I could try again deinstall everything and format the whole device, but I am not eager to do so again until I know this will help this time.
You could try clearing the cache on one of the apps that is causing you this issue and see if it will then work updating. Otherwise try installing the app and then reinstalling from whichever app store you are wanting to use - it should then try to install the uptodate version.
Clearing cache does not work. Same for deinstall/reinstall, independent from the app store in use, it only effects that I cannot install the respective app at all. Now I lost Youtube app for example, luckily I didnt trz it with Whatsapp. However, Whatsapp is running out (30 days to update)…thus I am in the need to resolve this problem sooner or later.
Hi
My storage problems are gone since I have updated to FP OS 1.8.
In the moment its beta (release candidate), but very stable.
You can download it from http://forum.xda-developers.com/fairphone/general/fairphone-os-1-8-release-canditate-t2955799/post57115103#post571151033.
Best regards
Bobby
Thanks @Bobby
For anyone that reads Bobby’s comment, I would add the extra disclaimer that there are a few bugs in this release that are being worked on still and you may loose your homescreen setup as part of the install so if you’re thinking “Oh good, upgrade time” you’ve been warned 
After endless hours spent in the forum, I’ve finally found a solution that works (for me, at any rate). Like so many others, it seems, some of my apps wouldn’t update any more, others couldn’t be installed in the first place, Android claiming there was insufficient storage. However, there were GB of free storage.
As suggested in Storage update: No possibility to move apps, I installed the Link2SD app and, in settings, changed the “installation path” (“Installationsort” - I’m using the German version) to “internal storage” (might as well work with “external storage”, though!). And… Bob’s your uncle!
Thank you, FFFan!
After the unified storage update I had the same issue: I could update some apps - and some not. I even tried a (second) factory reset.
Your solution finally helped.
Edit: I suppose that the source of the problem is a setting while using the old OS version 1.6 (with no unified storage). I had the setting to save new apps to the bigger “Phone Storage” and not to the small “Internal Storage”. This setting was probably kept even during upgrades to unified storage and to OS version 1.8 while the “Phone Storage” no longer exists.
It’s really important while using Titanium Backup to opt-in the setting “migrate systemdata” (German: Systemdaten migrieren) in the settings -> restore (deutsch: Wiederherstellungen) before using the backups.
After using this after my first try I had no problems with two FP after storage upgrader.