Having this error message trying to update your iPhone 5s to iOS 9.3?
Unable to Verify Update
iOS 9.3 failed verification because you are no longer connected to the Internet
I have encountered this behaviour on a iPhone 5s device and it seem that this is also occurring on older devices such as iPad Air as well.
Apparently, Apple temporarily pulled out this update for older devices because of installation issue on older devices. We have to wait for a resolution at this point.