I had the same problem after upgrading to a unified storage partition. Clearing just the cache was unfortunately not a solution, so I did a factory reset following these instructions (including “wipe cache partition”). After that I used Titanium to restore my apps one by one, excluding all Google related apps. For me this solved the problem, although it took some time to fix it, I’m now very happy that I can enjoy the full storage capacity.