I am also experiencing the same issue following a iPhone 6 device hardware failure and subsequent warranty replacement. I attempted iCloud and iTunes restore. Both restore methods produce iCloud and Apple ID verification failures. I made multiple restore attempts turning off find my iPhone, location services, restrictions, logging off Apple ID and iCloud before restore, changing the time, etc... No issues with factory restore to 9.2 but not having my data isn't acceptable. Backups require the device to be 9.3. I too am able to access my Apple ID and iCloud on other iOS, OS X, and Windows devices. I changed my passcodes and noticed a different error with a wrong passcode. With an incorrect password, the error states the ID or passcode is incorrect. If the correct passcode is entered, the verification failed error is produced. Obviously the device is able to communicate with Apple servers and the issue is with the beta software and apple's backend. I think the ball is in apple's court on this one.