Exactly the same problem for me - except mine is the same phone, not a new phone.
I had to wipe my iPhone clean and so later tried to restore it, opting to restore from previous backup. During the restore of previous backup data I get the message on my iPhone "Restore Failed. There was a problem during restore. Please restart your iPhone and try restoring again."
No matter how many times I perform the restore, I get the same message. There is NO error number, and there is NO error in iTunes - only on the iPhone screen. I too have no gs.apple.com entries in the hosts file on my Mac.
I have restored the iPhone backup file itself from several different points in time from my TimeMachine backups, but all of them produce the same result.