Insufficient Storage Available I have a Nexus 4. Whenever I try to install any app, no matter how small, it says "Insufficient Storage Available".

I have aggressively deleted photos, uninstalled apps, cleared the app cache, and now I have 315 MB free (according to Settings > Storage).

But it still says "Insufficient Storage Available" when installing from the Play store. (For any app; I have tried with dozens.)

I cannot even install the apps that I removed two minutes before. (WTF?) I have restarted several times.

What can I do to fix this erroneous error?

(Note: I don't have any SD card.)
You didn't mentioned it's a rooted device or not. 

When I face similar issues I manage to fix this issue in this way. This is a permission related issue. I guess you face this issue when you're trying to update or install previously uninstalled apps.

When you are uninstalling app, it remain some leftovers in "data/app-lib" directory. Therefore, carefully check app that you wish to install leftovers are in this folder and delete those folders. 


Go to "/data/app-lib/APP-PATH(that has this error)/lib" and delete its all the sub folders. Then delete APP-PATH folder.


If its not work you can factory rest your device to fix this issue.