Every time I go to install a new app, I get the message "Insufficient storage", and an unable to install anything!
I have spent quite a long time moving every possible app to the SD card, and still most of my space on the phone is gone.
However, that isn't even the weird part. I have 250mb of free space on my phone, and it still unable to install even 300kb apps. I read this answer, but that is mentioning space as small as 13mb remaining, while I have as much as 250mb!
How much space is required on my phone to install a simple 300kb sized app???
Btw, I am running the newest second newest (this problem is getting so bad, I can't even install an update) update on an HTC Thunderbolt, which I believe is android 2.3

Settings | Applications | Play Store | Clear data. Might help to "Force Stop" the app first. – Al Everett May 14 '12 at 20:15