Before you try a full restore, give this a shot, if you haven't already. I don't think it likely to solve the problem, but it's a lot less trouble to go through than the restore.
Reset All Settings: Another, somewhat more drastic thing you can do is Reset All Settings. You'll find this under Settings > General > Reset > Reset All Settings. It won't erase any of your content, apps, or accounts; but you will have to go through most of your other settings and re-tweak them back to your liking.