Restoring from an iCloud backup not working

Restoring from an iCloud backup on my iPad (iOS 8.0.2) isn't working.
After choosing a Wi-Fi network, signing into my iCloud account, agreeing to the terms and conditions, selecting a backup, and entering my iCloud Apple ID password, it just immediately says "Could Not Sign In - There was a problem connecting to the server."

I can set up my device as a new iPad, sign in and use the App Store with it, but it just can't sign in to restore all my purchases and data. :/

I've never had an issue restoring from an iCloud backup before. I guess I should also have made a regular backup in iTunes before I restored…

Any idea how to get this to work?