If you have root, delete all of the folders on the path:
/data/app-lib/
And then restart your device.
I had this issue many times, and this fix worked for me each time. It even has an XDA thread.
I write all folders, because if there is a problem with one app, there is a good chance you have this issue with other apps too. Plus, it's annoying to find just the folders of the problematic app/s .