Cannot update even tiny apps, despite clearing cache numerous times, and conducting "Delete Dumpstate/logicat" and phone showing 103MB available. Jelly Bean 4.1.2 (yeah, I know -- old, but need to wait a couple more months before getting new phone).
Many updates will take much more space than that. Have you tried clearing out the individual caches of different apps (browser, facebook, etc.)? Also, you may want to consider uninstalling any apps you really don't use to free up space. If you have a SD card in the device, you can also move photos, videos, music, etc., over to the card to free up even more.
And, once you have moved, cleared out and/or uninstalled, be sure you restart the device before trying to update again.
App Cache Cleaner Pro empties all the caches with one button (if I choose). This is a recent change in behavior. As far as the SD card goes, all of my pictures go to the SD card. I have cleaned a few stragglers out. I have 114MB of free space (after clearing caches), the program I need to install is 17MB. Really "feels" like something needs to be reformatted. My phone is turned off every night, BTW.