Done it. Tried restoring from iCloud too per Apple support. I've come to the conclusion that I'm either going to get miserable battery life or I'm gonna have to ditch my backup and just lose my app data and SMS database :/
There
is one way to save your app data. You'll need two computer programs: the
iPhone Backup Decoder (free, Mac) and
iExplorer (free, PC/Mac). You take your latest backup, and run it through the backup decoder. It will spit out a nested folder with all of your data. Next, take your restored phone that has all of your apps installed. Open them. If they download/sync from iCloud, yay. If not, close them and
remove them from the app switcher.
Next, open iExplorer. Navigate to the Apps folder. Find an app you need to restore (let's say Angry Birds). In your nested folder will be the Angry Birds folder, with a plist and a library archive and some other ones inside. Just drag the contents of the folder over into iExplorer and drop them in the Angry Birds folder. It'll paste, ask if you want to overwrite, and say yes.
Go ahead and open up your app, and if you dropped in the correct files, you should have all your levels restored. Rinse and repeat as necessary.
The page about the backup extractor will link to a free mac app that will let you read the SMS database on your computer, but I don't recommend trying to copy it back. I never got that to work for me.