I think I've found a market fix that is simple and seems to work, need testers.
note- as always, backups are recommended before attempting any fix
Download
com.keramidas TitaniumBackup from the market. I do not know if it requires the pro (paid) version, I have the paid version installed, so I need someone with the free version only to test please.
Open it, let it load fully, then press your menu key. Select the more tab, then select "Integrate sys Dalvik into ROM." There is an "Undo sys Dalvik integration" option you can use to undo it should it not work out for you.
Since doing this, I've been able to update everything I had not been able to, and install apps I had not been able to. The messages I had been receiving that were fixed are insufficient space messages. I doubt this will help with any other type of errors. Please let me know if this helps you.