“Insufficient Storage Available” even there is lot of free space in device memory

Here’s a very simple solution that works on my Samsung Galaxy S II and Note 1; I have no idea about other models:

1. Open the phone app and switch to keypad.
2. Dial *#9900#
3. On the screen that appears, click on the button labelled “Delete dumpstate/logcat”.

I’ve restored about one GB of system space this way.