I just stumbled upon multiple "low space / not enough storage" error messages on my Galaxy S2.
I never thought there would be such a simple solution:
Just delete all the log files in the device memory.
How ? Easy ! Dial *#9900# on your phone and select option 2 “Delete dumpstate/logcat” in the prompted menu. I restored 500MB space with this little "trick".