I had the same problem. I did try many ways to fix it. But problem returned after a few hours or minutes. I had call with Apple support. They said, problem started at iOS8, iOS9 fixed it, but there are some unreparable bug in backup phone.
I made everything, it takes me 6 hours + night to download data for apps (cca 35GB). But after this is iPhone faster and spotlight works perfectly.
Then only one clear way is:
- disable Find my iPhone
- restore iPhone from iTunes (downloading and installing iOS)
- initialize iPhone as a NEW! without iCloud account
- add iCloud account and synchronize you want
- manualy install apps you want
It looks easy, but you haven't forget for your data!
You have to prevent losing data. At first, I have to say, I didn't found how to save and restore Messages, because messages aren't part of synchronization, only saved in backup. But backup you cann't use for restoring, because there is bug for that spotlight doesn't work. Then you have to know, YOU WILL LOSS ALL MESSAGES. You can backup them with any app from store or you can use any unoficial app for reading backups (iTools, iBackup Viewer, iFunBox). I didn't test it, you can do it on your own risk. I don't use POP3 in mail accounts, only IMAP or Exchange protocol. Then I didn't backup emails. IMAP works as backup.
You can do these steps:
- write list of apps you have installed
- check if these apps are using iCloud or any different cloud and save logins, or you can save data from these apps by the iTunes your computer if supported.
- create screenshots of each screen
- create screenshot or write list of favorites contacts
- photos you can save to computer or (I did it) set photo library to iCloud. If you have small free space on cloud you can buy extended space temporary for this process. ($1/50GB/month) You have to wait with restoring to complete library synchronization. You can see uploaded photos at www.icloud.com My 1000 photos/videos library takes about 7GB.
Then after this you can connect iPhone to computer and start restoring.
When restored, add manualy iCloud and Stores account. After a few minutes you will see contacts, callendar, notes are synced after first use. Dont forget turn on photo library on iCloud, you can do it later.
Next you can add your other accounts (I'm using Gmail) and install apps. You can do it from the iPhone or you can download apps with iTunes and sync later.
If you are using offline maps, you will have to download maps again.
If you have personal ringtones, you have to sync from iTunes, then if you had presonal ringing for contacts, after syncing ringtones will works as before.
Set all settings you have to change from default, for example I disable Siri recommendations on spotlight or turn off GPS functions for ads and apps I don't want to allow GPS.