So I've seen this error coming up in many forums, mostly people advice a factory reset, reflash of the ROM or something else. As far as I know this solution has not been posted in any other forum(please correct me if I am wrong). Now, this error usually happens to me when I've installed the app before, uninstalled it and I'm trying to install it again(or) when I try to install a paid app from the play store I get an error (-24) or the insufficient storage error. All these errors have the same solution. I've tested it on the HTC One, Note 10.1 and the S3.
Ok here's the solution(I take the app Modern Combat 4 as an example here). I also assume that you are rooted.
1.) Download the app Root Explorer or Root browser or any other similar app from the play store.
2.) Next in root explorer go to /data/data.
3.) Look for the package name of the app you're installing. Eg. For MC4 com.android.gameloft.ANMP.GloftM4HM.
4.)Delete the package.
5.)Try installing the app now, it SHOULD install.
Note:If it still doesn't work for you, go to /data/dalvik-cache and try locating the file and delete it.
I hope I helped someone here because when I had this problem it pissed the s**t out of me and I couldn't find any real help. If it helped you please press the thanks button!!