I can't install iOS 9.3.1 even though its downloaded. It fails at verification. My phone is connected to the Internet and it's working perfectly (yes I've tested). I've restarted my iPhone but no luck. I'm currently on iOS 9.3.
Usually such an error will occur when one or more Apple servers serving that area is down or perhaps it might have to do with either some proxy settings on your providers side if not on your phone side as I've often seen such responses with people having Global HTTP Proxy enabled on their iPhones.
I'd suggest you to try and connect to a WiFi network and try again.