Firstly what version of PA are you updating too? One of the Beta's with Halo?
What did you wipe before you flashed the zip?
Usually I just boot to recovery, flash the ROM zip, Gapps, wipe Cache and Dalvik cache. This is commonly referred to as a dirty flash and doesn't wipe the data partition with your user apps.
You have two options, if you have backed up your apps recently in TiBu then restore from there or restore a nandroid if you did one before the update.
I had that message when flashing my Nexus 4 recently, the only way to fix it was a clean install.
Backup your apps using TiBu.
Boot recovery, factory data reset, flash ROM zip, flash Gapps, wipe cache and Dalvik cache, reboot.
Try another dirty flash first but if you get the same message then a clean install is the only way forward.
Sent from my Paranoid Nexus 4 using Tapatalk 4 Beta