Error when restoring a iOS 4.3.5 backup onto a iOS 5 device
After the restore fails, take a look at the phone and see if your data is installed.

Restoring data after every major iOS update has failed on me, but after I put the apps back on, all my data is there.  Pick a few apps that you know contain data (Contacts, games, documents, Notes, login details) and see if your data has at least been restored.

It takes some time to put the apps and usic back on, but major iOS updates only happen once every couple of years.