Setting up new iPad 10.9 in. At Restore backup from iCloud got the "Verification Failed! There was an error connecting to the Apple ID server"?
Other replies mentioned time, and I noticed the iPad was dispaying wrong time. I had to factory erase; setup manually without any restore - then time was OK. Then Factory erase, setup manually - time looked wrong again, but Restore backup from iCloud worked this time.