I had exactly the same thing. What I did was delete all the apps from the phone via iTunes, then backed up, restored, jailbroke again, then reinstalled all the apps one by one.
After that they worked.
Bit of a pain but at least it did work again. I guess the backup/restore process with JB between somehow messed the apps up on the restore.