Pues navegando por xda, me he encontrado con esta noticia que nos interesara a muchos de nosotros.
Cuando congelamos o desasistamos con cualquier gestor, como pueden ser titanium o rootexplorer o cualquier otro tenemos que tener en cuenta una Apk de sistema que nos puede fastidiar nuestros propósitos.
La Apk en cuestión es preloadinstaller.Apk
Esta Apk lo que hace es, cuando reinicias el dispositivo automáticamente te instala las Apk que tu hayas congelado o desinstalado anteriormente.
Es importante tenerlo en cuenta para no encontrarse después con sorpresas desagradables.