No es que sea difícil, es que es raro que un elemento del sistema no funcione tras un formateo. Te lo preguntaba por si instalabas Titanium, Autostarts o alguna app que parase procesos justo antes de que te dejase de funcionar y sin darte cuenta tuvieses ese proceso parado. Si he entendido bien, aparece al formatear y luego desaparece del cajón y del Administrador de apps, ¿cierto? Me parece tan raro...