I believe this is a common issue, as I've read every post I can get my hands on, but none of the proposed solutions that I've attempted have resolved my issue.
I recently rooted my VZW S3, using CyanogenMod (10.0.0-d2vzw), so I'm at Android 4.1.2. I don't have many apps loaded onto the phone (GMail, Maps, Evernote, Dropbox, Twitter, USAToday) as well as photos saved onto the internal memory.
When attempting to download/install app updates, I'd always get hit with the insufficient space available error...so I found a resolution that suggested using [redacted] to fix this. It appeared to work, but today I now get a persistent "Storage space is running out" error, which has rendered any data connection (wifi/4g) useless.
Per other recommendations, I tried using 1Tap Cleaner, then Link2SD to move photos to SD, but that even threw an error (pkg: /data/app/com.google.android.gm-2.apk Failue (INSTALL_FAILED_INSUFFICIENT_STORAGE))
I then tried Send to SD card, and seemed to work at first, but hasn't corrected the issue.
When viewing my storage settings, they currently are:
Internal: Total, 12.05gb
Apps: 820MB
Pictures: 723MB
Audio: 20k
Available: 80.95MB
External (SD card): Total, 14.93GB
Available: 11.44GB
Obviously something doesn't make sense if I have the free space on the SD card (or so it says) and I find it hard to believe that the ROM is taking up almost 11gb of internal.
Any and all help you can provide is greatly appreciated.