I got this error message when trying to install Viber on my phone. A 20 mb application would not install even though I had 3 gb of free space on my phone. This issue can sometimes happen if your app cache is full but that wasn’t the case this time. If you haven’t tried that yet, you should do that first.
Install an app cache cleaner from play, rinse the cache and you should be good. But not this time.
Providing you have sufficient storage on your device, you have rinsed your cache and even freed up even more space than required and it still doesn’t work. There’s one more step you can take that worked for me. You have to have a rooted phone for it to work.
Open a file explorer with root permissions. Go to the root (/) folder of your phone and search for the app you are failing to install. I searched for viber. I found a few random files and just deleted them. But be cautious so you don’t delete anything important. For some reason, viber had left some files on my phone while failing to install the first time and they never got removed. After deleting them, I was able to install viber.