New restored iPhone getting "iTunes couldnt not back up the iPhone because the backup session failed"
I'm working through the same issue and it seems to have something to do with the sim card. Is your sim card valid? meaning do you plan to actually activate it for voice and data and use it as a real phone? In my case, I already transferred the number to my iPhone 4 and just want to give it to my kids to use as if it were an iPod touch. So I took it to the mac store and the genius had a few suggestions but didn't help very much, He suggested using iTunes 9.x which you can still download.  I tried that on an old mac I had but it didn't help.  He even suggested jail breaking it which I'm technically capable of doing, but from what I've read I think it has to first be functioning and connect with iTunes before it can be broken so it's a chicken and egg thing.  So here is what I think is happening, (no solution yet though). When the first iPhone was originally released, you used to have to take it home and hook it up to iTunes to activate it.  They didn't do anything for it in the store or activate it on the spot. So your phone is currently in the same state after the restore. It's trying to go through the setup process, but the number registered on the sim card is already disabled or somehow marked as invalid and some kind of unexpected error occurs that prevents it from continuing with the setup process.  

Now here is an interesting thing...  even though I couldn't restore it, I offered to loan it to a friend 2 months ago who lost his iPhone. He just wanted something to use while he waited for the 4S to be released.  He went to the ATT store and told him he lost his original iphone and wanted to use my first-gen instead. They didn't even look at the phone, but they gave him a valid sim card to take home. He was able to do the setup process at home and use it just fine. So I suspect something about having a proper sim that is willing to be activated with a real account helped him get running.  However one other difference is that he is using iTunes on windows, I'm all mac... (Tried this on 3 different machines so far.. powerbook running snow leopard, and an iMac running lion, both with the latest iTunes, And finally mac mini running iTunes 9.2.x).  

Update: I had a bootcamp partition running XP. Used it to download iTunes 9.x for Windows.  Still encountered similar errors. (Sorry, don't have exact code).  I still plan to try simcard replacement to activate old phone with current account.