Algo mas he averiguado.
La aplicación mp3 dowloader la tenia instalada desde hace un tiempo. No la usé casi nunca.
Cuando instalé 4.3, desapareció de mi escritorio y fue cuando empezó a enviarme notificaciones.
No podía desinstalar porque no me aparecía en mis aplicaciones, así que la volví a instalar y desinstalar.
Espero que asi se arregle el problema.
Ya os contaré