All of the above suggestions will work - for a while. Dialing *#9900# (and making sure you start with an asterisk) then selecting Delete dump will clear some of it. Force Stop all of your apps helps (or at least extends battery time), and clearing all the cache with the Cache Cleaner app helps. The problem isn't how much storage space you have - it's the memory space. The phone isn't releasing the memory for use. If you look at how much memory is available it will still show an alarming small amount, and if it's anywhere from 200MB to 250MB available memory you won't be able to download and install new apps no matter how much storage space you have.
The next thing to try - go through your apps, select the ones you don't use but can't uninstall, like most of the Google apps and Kindle, and select Uninstall Updates for each of those apps. That will clear tons of memory! You should be able to install your new apps.
Then - It may be a pain, but don't set your phone to automatically update the apps. Do them manually and never choose the ones you don't use, like Google newspaper, Google books and all that other junk you can't uninstall. It should keep you going for quite a while before needing to do this again.