Are you restoring from a backup each time? If so, and the problem exists each time, then the problem is in the backup.
Do a restore as a new iphone, but do NOT restore from a backup, then sync your apps/music/etc in iTunes.
Don't restore from a backup, set it up as a new phone.