I ran into the same problem. But I got around it by turning off sync the content stored on my phone. {photos, podcasts, etc}. This made the back up step fast too
After that the "restore" succeeded without any problems and then I was able to put stuff back.
After that the "restore" succeeded without any problems and then I was able to put stuff back.