As I had the same problem with a brand new iPad, I've been talking to the apple support since yesterday, they tried everything I also did find on the net, like checking the hosts file, trying other internet connections, resetting internet settings, but as nothing did work, they told me they would investigate the problem further and contact me again today.
Meanwhile I tried to update/restore some other iPads, OTA as well as with different Macs, and got the same error on every device every time.
Today the support called and informed me that the problem is with the Apple update servers, but should be fixed soon. During the conversation, the download suddenly worked and I could finally update the iPad.
I hope that it works for everyone else now as well.