Insufficient Storage Available During Update
Same kind of a situation happened to my SAMSUNG GALAXY S2 and I could solve it by following these steps:


Open the phone app and switch to keypad.
Dial *#9900#
On the screen that appears, click on the button labeled "Delete dumpstate/logcat".