Insufficient storage message when attempting to install app
This happened to me sometimes when I uninstall any apk, and try to reinstall it. I use to search for some residual files of the prior apk, and android said you that you don't have space but actually is that it can't install the apk, it can't overwrite the residual files.

Maybe this is your case. It always fix this situation for me.