I get exactly the same problem and indeed posted something on here myself, no replies yet though.
At one point I couldnt update or add anything. What I ended up doing with removing some of the apps I ahd on the SD card - which also made more room free on the phone itself (I can only assume the phone has some data stored on it to access the app?)
Anyway, having done this and restarted the phone, I sometimes get it to work.
HOWEVER, if I try again say the next day, not a problem!
I wonder if perhaps there is an issue where when you try and update things the phone confuses itself into thinking there is no room to install things (I guess it needs some room on phone to run the install - maybe to keep the settings when it deletes previous version of app or something), anyway, at some point it seems to refresh this information so when you try it again the next day say, it behaves as if there was never a problem!
I have also found that sometimes removing the app and re-installing it can help.
One of the other things I did when I was having a severe case of this problem was remove a programme that I had on a trial that had run out, I think that may have had an impact on me being able to update and install things too as removing it seemed to improve things!
Hope some of this is of help
Cheers
Him1977