A friend of mine has a Samsung Galaxy S2 with 16 GB of internal memory and a 8 GB SD card. I have installed Cyanogen Mode 10.1.3 (Android 4.2.2) a while ago with the Google Mobile Services.
It seems that the internal memory is fragmented into two parts:
I scrolled down here:
I do not see how this adds up to him having to more free memory to install new apps. How can this be fixed?