not trying to rehash a "solved" thread but Im having this issue and then some.
First, I tried Darksides wipe script and tried to restore the boot and install a new rom, then install the backup, all to no avail. I tried everything. When you get this error, it seems (at least from my experience) that your only hope is to restore from the stock 4.02 google image and then restore from the nandroid. This first happened to me when my phone dropped and off the couch and the battery came out. It seemed to have corrupted the sdcard, or, at least that was my guess.
However, upon redoing everything to stock and restoring the nandroid (even upgrading to the latest ver of clockworkmod recovery), the problem comes back. Im worried about permeneant damage, possibly, but it makes no sense that I would be able to revert to stock and have it working fine. When I reverted and restored from my nandroid, everything worked flawlessly. Then, today, I turned off my phone (which is a rarity, if ever) and it wouldnt boot back up a few minutes later. Bootlooop and the dreaded "error while restoring data!" message. Im going to revert to stock again and start completely from zip, no nandroid. Its possible that the nandroid is corrupted I suppose but i dont believe it would let me restore it than. Any ideas? Could this be from me leaving my phone on practically all the time, without ever turning it off? or the battery coming out while in use? (which makes sense in theory but I've done a battery pull countless times and never had a problem like this). Would there be a way I could determine, for sure if its a hardware problem? Verizon Nexus (hardware ver 9 I believe) now running JB Sourcery 2.0 (from team sourcery...an AWESOME rom, so I dont believe it to be that.)