This sounds like what we happening to me and a lot of people on day one (our day one, anyway - it took a while before some phone models were admitted). First time I got stuck between two stages of updating in just the way you describe; it downloaded but wouldn't install. I did a full hard reset from the menu to wipe the phone and start fresh, said "no" to the offer of using one of my previous backups, and everything went smoothly after that.
Obviously, it's a last resort, but it's not too much trouble to reinstall your apps again and sort out your settings. If nothing else works, do that.