Do you have antivirus that can install programs while scanning them? I know my antivirus can be setup to do safe installs, but it also greatly increases the error rate of installation. In my case, I believe it is because the phone runs out of RAM, since my AV makes a copy of the apk-file, then install from that, while not cleaning out of RAM the original, in addition to the AV requiring more RAM to do this.
I have to bypass my AV safe installation feature for any installation where the apk is above 1GB, and do the scan AFTER installation.