Reinicia en modo recovery el móvil (puedes hacerlo aunque no este rooteado) y haces un wipe caché, eso debería solucionarte el problema, incluso quizás lo haga el simple hecho de reiniciar, si no te funciona eso, flashea con Odín la versión 4.0.4 descargada de sammobile.
Otra cosa, supongo que has actualizado desde 4.0.3 a 4.0.4, si lo has hecho desde 2.3.6 deberías hacer un wipe data.