I hope I can add some solution to those of you still struggling tonight. I'm sure Apple will come out with a fix, but if you need your device ASAP, as most of us do, this might help. I failed first few times, and then this worked. First, I jumped from ios7 to 9, so that might have contributed to my prob. But, here is what I did that finally worked:
First, hopefully you saved a backup on iTunes prior to trying your ios) upgrade. That is critical. You will need whatever backup you have later, after the Restore.
Second, go on your other apple device or PC to iCloud.com and disable your "Find my Phone" service for the device that you are trying to upgrade. Actually "remove" it from the "find my" service, then sign out of that completely. You might have tried this already, but I think that it is a combination of issues that, if done together, work as a solution.
Third, plug the device you want to upgrade into iTunes, freshly, as if you were just planning to synch, regardless of what you've done previously. As soon as you see your device, go to "Summary" and select "Restore." Make sure that your device, whatever stage it was in when you connected, is ready to accept activity from the Restore. That is, if you have a password, put it in so that the system can quickly access it for changes. If it's not "ready," you could lose the process and have to start over.
Fourth, When you are asked if you want to back up prior to the Restore, I said "No" to go directly to restore, (but I had backed up prior). You want a totally clean restore. This is what worked for me. I did not try it the other way. (Make sure you've backed up your data into ITunes either way).
Fifth, when the Restore Page comes up on your ITunes, select your back up, do not treat it as "new" device.
SIxth, when the Restore is complete (be patient), and you see the "Hello" screen on your upgraded device , swipe ONLY that Hello screen first. When you see Location Services screen, select NO or NONE for LOCATION SERVICES, (You can change this later after you've successfully upgraded).
Seventh, and this is KEY, when the question comes up for a Passcode, DO NOT CREATE a PASSCODE. Again, you can always add one later, but this seems to be an issue, together with Location Services and Find my XXXX. I worked this whole process with the passcode and Location services prior, and it failed.
After you are past the Passcode and Location Services pages, it will bring you to your Apple ID page, and then you are home free!! Put in your Apple ID, and synch your data from iTunes (that should be underway from your backup restore), and get back to normal, Don't forget to turn your Find My Device back on, and add a Password once you have all your data back, etc.
Good luck guys. I hope this helps!