I had the problem even on the original android 4.1.2 rom (with the default/not updated play store app), and I currently have Lewa OS (A chinese custom rom), which still has the problem. There is enough space in every possible install location (I've tried setting it to the SD card and the internal storage). The alternative chinese app market has no problem installing applications right after downloading them.
Any help is greatly appreciated.
Phone Specs: gsmchoice.com/en/catalogue/zte/bladec/ZTE-Blade-C.html
Lewa OS Website (in Chinese): lewaos.com/main.html