Thank you for posting this. I was in this boat and I don't think I would have figured it out otherwise. I owe you a beer.

Also, in case anyone else is reading this, I was also getting mysterious "Unknown Errors" from iTunes when trying the restore, it was because I hadn't updated iTunes to the very very latestest.