Seems to be a bug when updating from iOS 7 to iOS 9 (skipping 8). I solved my issue by downgrading to 8.1.4 as it is still signed by Apple, restoring my back up and then updating to 9 and it worked. I detailed some instructions in another post and I'll paste it here:
Hi all, I HAVE A FIX!
Spent the last 12 hours pulling my hair out trying to find a solution to the problem - and I think I have one!
Did a bit of Googling and a guy on Reddit had the solution that worked for me. I upgraded from iOS 7 to iOS 9 and that caused an issue when I tried to restore my back up. However, by downgrading to 8.1.4 (as it is still signed), restoring the back up (my files all returned, but my apps disappeared strangely..) and THEN update to iOS 9 and it finally worked.
Here's the solution:
Finally fixed it! You have to downgrade to 8.4.1. Outlined the steps below.
Step 1 - Backup your pictures! Even though you can't get to your phone and use it you should still be able to backup your pictures
Step 2 - Download IOS 8.4.1 for your iPhone or iPad from this site (Choose the right one for your model) --> https://ipsw.me/8.4.1
The file was taking a while to download for my phone so I searched the filename on Google and downloaded from Mega.
Step 3 - Reboot phone into DFU mode - hold down power button and home button - when it reboots let go of power button - still hold home button
At this point it will ask you to connect your phone to iTunes - will have to connect phone to the computer.
Step 4 - Hold down the Option (Mac) or Shift (Windows) and and then click restore.
Step 5 - Browse to the 8.4.1 file you downloaded and select it. This should restore to the previous IOS version. Note: This will wipe phone.
Step 6 - Restore from backup. Hope that you backed up before attempting to update.
Hope this helps you all! :-)
EDIT: Reinstalled the apps by going into the app store and viewing my purchases - they're all there. Downloaded them all and they all sorted themselves back into their categories as I had them before. Whatsapp conversations were also restored so it works. HOORAY!