Es un error comun en todas las versiones de Android (creo desaparece en lollipop), pasa por un error de residuos de apps al desinstalar varias, esos residuos son unos archivos .odex que pertenecen a apps que desintalaste.
Solución facil: con Lucky Patcher (necesitas root) ir al apartado inferior Toolbox, seleccionar Remover correcciones y respaldos (almacenamiento insuficiente), se reinicia, despues la otra opción, Odex all system apps, y listo.
Solución manual: Se necesita un explorador de archivos con permisos root, en el explorador de archivos buscar archivos .odex que correspondan a apps que ya no estan en el equipo, ya sea en raiz--data--app, o en raiz--system--app.