Have you actually rebooted into recovery and tried a restore from there instead of using the app?ssethv said:
Also make sure there are no spaces in the backup's name. That has caused a lot of people a lot of grief in the past.
Sent from my iPhone 4 running BAMF Sense 3.