I came across INSTALL_FAILED_INSUFFICIENT_STORAGE error when I tried to batch install about 50 apps in sd card directory using adb shell after a full ROM update.
# cd /sdcard/batchInstall
# for x in *.apk; do pm install -r $x; done
Some of them installed, but many failed with the error INSTALL_FAILED_INSUFFICIENT_STORAGE. But I had plenty of space in both internal and sdcard. I noticed that all the failed apps had space in their name. I batch renamed them to remove space with '_' and tried again. It all worked this time. Hope this info will help someone with the same problem.