If you Restored to Factory Conditions, checked if it eliminated the problem, then Restored From Backup and are still experiencing the issue, it's likely that the corruption is part of the backup, do restoration just brings it back.
In iTunes Preferences, select the Devices tab. It should list all the backups you have saved. If there is one that precedes this issue, Restore using that backup.
Otherwise, unless someone else has other suggestions, you'll likely have to restore as a new device and start from scratch. Whatever you have in iTunes will be synced once you set up the device with the same ID and all your iTunes, App Store, etc, purchases can be re-downloaded for free.