Solving iOS 6.1.x “Unable to Verify Update”

I went to do an iOS update the other day on my iPhone 5. I was trying to update from iOS 6.1.2 to 6.1.3. I was stopped after receiving the message “Unable to Verify Update”.

I tried restarting my phone, reran the update, same problem.
I tried turning wifi off, then back on, same problem.

Here is what solved it.
In iOS settings turn off wifi, then restart your phone. After restart, turn wifi back on, then go back and try to do the iOS update again. It should now say something that it is checking for update. In actuality, there was a newer update out there which I believe was trying to get inserted. In my case I now was presented with updating to iOS 6.1.4 instead of iOS 6.1.3.

I am now successfully updated to the latest iOS version
I suspect this approach will work with other iOS 6.0.x versions as well that receive this message.
Hope this helps.