Decided to do a full hard reset this morning, including wiping the cache etc. This seems to have solved the problems: all apps do install/update nicely now.
I did test Titanium Backup by restoring some apps that caused problems before, e.g. Twitter, and now those update fine. So Titanium Backup can be used, but perhaps it causes problems when restoring system apps like Google Play. I’m not going to try that and in the future will be more selective in which apps I restore.
BTW, a hard reset did some interesting things. First the Google apps were already installed, so the widget was already greyed out saying that it should be deleted. Furthermore, upon boot the normal Android configurator asked for my Google account; subsequently it seems that the FairPhone configurator removed this information, causing all kind of new update errors (906), which prompted Google Play to request my Google account details again, and everything was fine.
@Cathal if you did not update to the “unified storage partition”, then you might indeed have ‘insufficient storage’ to update/install certain applications. This update can be performed after updating the FairPhone to version 1.6 (cherry). However, this will remove all data from the phone, therefore many people like to make a backup first. Titanium Backup is a tool to make those backups, but there are others. Please follow the link above for more information about repartitioning and backup tools.