After grappling with this for rather a long time on my phone and not really understanding where the storage was going I found the following thread: http://forums.androidcentral.com/samsung-galaxy-s-ii/272384-galaxy-s2-cannot-download-updates-new-apps-2.html.
Essentially just dial *#9900# from the standard phone dialler and choose the second option "Delete dumpstate/logcat" from the options. Easy.
Having seen this on a friends phone and been unable to resolve it I now understand, I had > 800MB of log files, not sure what use these will be of to anyone, but at least I now have 50% of my diddy little 2GB ROM partition free so that I can put some of the apps I had removed back on.
