Yo he tenido problemas con las apps de mensajería (telegram y wahtsapp). No me entraban los mensajes hasta que encendía la aplicación.
1- He reinstalado las gapps sin que eso me solucionase el problema.
2- He reinsalado la rom sin que eso me solucionase el problema.
3- He desinstalado las apps y vuelto a instalar, solucionando el problema.
Conclusión: El titanuim backup va muy bien restaurando datos de aplicaciones, pero te puede joder cosas como que las aplicaciones de mensajería se registren en la red para recibir los mensajes push.
Por cierto, me he dado cuenta que en la primera instalación no tenía el Walkman, me ha aparecido tras reinsalarla sin hacer instalación limpia (la primera instalación sí que ha sido limpia)