Tienes una rom liteada? Porque si es asi será por eso.
Para que funcione necesitas el "Samsung push service"
A mi me paso lo mismo porque para aligerar mi rom, en vez de borrar cosas las había congelado con el titanium backup, entre ellas el "Samsung push service" lo descongele y ya me funcionó bien.
La apk se llama SPPPushclient_prod. apk debería estar en system/app