Hola, yo he usado el Airpush Detector para eso mismo que te ha ocurrido.. lo que hace el programa es que te dice si tienes algun programa instalado que te meta publicidad, y si quieres, lo desinstalas.
Otra opción es que con el Airpush detector averigües que programa es el que te mete publi y te vayas al gestor de aplicaciones, busques el programa y deshabilites las notificaciones. Creo que funicionaría.
Espero que te sea de ayuda. Saludos
