how to solve "Verification Failed! There was an erro connecting to the Apple ID server"?
I had this problem recently when trying to set up my new iphone 7. Finally figured out that even though the phone said I was connecting to my wireless network, the wireless router said that the device was not connected. I don't know why. To work around the issue I rebooted my wireless router. After that the router showed the iphone device connected and I was able to authenticate to the Apple ID server.
I was also able to get around this by not connecting to wireless during the iphone setup and using cellular, however that doesnt work with restoring an icloud backup. For that, I had to connect to the network.
Choose "iCloud" icon
Sign in again on the redirected page to iCloud
Scroll down to "Devices"
Choose the device that is giving you that error and select "Remove from account"