Fixing insufficient storage available error on Cyanogenmod

Update: A commenter suggests using InsuFixer which simplifies this process greatly.

A few weeks ago Google Play started throwing an error the error "Insufficient storage available." I looked at my phone storage and saw ~4gb available. Annoyed, I googled around for fixes. Most forums suggest clearing caches, repairing permissions, or deleting random things out of /data/app. Of course, none of which fixed my issues.