No puedo desinstalar LA MAYORÍA de aplicaciones ¿POR QUÉ?

El problema es precisamente por usar root y haber dado permisos a todo lo que creías que era benigno.
Existen aplicaciones que cuando te piden permisos de root lo que hacen es adueñarse de la administración del sistema. Incluso si es con un buen fin y con tu conocimiento, eso supone un problema, y es que la aplicación, con todos los derechos, te va a impedir usar otra app (en este caso el gestor de aplicaciones) para desinstalar aplicaciones.
La solución es desinstalar cualquier aplicación que tenga permisos de root (y revocar los permisos de root antes de nada).
Si sigue sin ir correctamente, instálate Titanium Backup y copia los datos de las app que no quieras perder (por ejemplo los de un juego que se guarda en el teléfono y no en internet, o los de una app que no sabes cómo instalar de nuevo, etc). Sólo esos. No se te ocurra copiar datos de aplicaciones con permisos de root.
Tras hacerlo, formatea tu móvil. Recomiendo que lo hagas entrando en tu recovery y wipeando las particiones justas y necesarias (no borres nada que no sean /cache /data /dalvick).
Si tras hacer eso, sigue sin ir, asegúrate de guardar en tu SD una rom que funcione, ya sea custom o stock, o bien flasheala desde tu PC (no hagas experimentos, usa una que funcione) y haz una instalación limpia (es decir, formatea también /data).
Una vez que termine la instalación y el primer inicio y configuración, instala lo primero "Titanium Backup" desde la tienda, y restaura los datos que habías guardado. Reinstala tus aplicaciones (obviamente las que funcionan bien y no tienen acceso root) y tendrás todo funcionando y sin perder nada (incluso habiendo hecho un poco de limpieza, estoy seguro)
He dado por hecho que entiendes acerca de manipular Android, pero si alguno de estos palabros no te suenan, estaré encantado de aclararte lo que sea.

Gracias por tu tiempo y dedicación a mi problema.

Si no entendido mal me estas diciendo que borre las aplicaciones las cuales son precisamente para liberar memoria del movil que de otra manera no se puede, es decir sin SER ROOT.

Respecto a lo de formatear mi móvil, es posible hacerlo desde el mismo o tiene que ser con algún programa externo?

¿Restaurar a modo de fabrica no es como formatear? Lo hice en varias ocasiones....

Te cuento.
Tu no eres ROOT. Instalar aplicaciones milagros que dicen desinstalar cosas que vienen de fábrica no es ser ROOT. De hecho es por eso que dan tales problemas, porque se les da permisos que en realidad no pueden ejercer.
Sólo hay dos maneras de desinstalar aplicaciones preinstaladas: o la marca de tu móvil lo permite mediante su programa asociado para PC, o bien tienes que instalar una Custom ROM limpia.
Restaurar de fábrica y el primer paso que te he dado (borrar /cache /dalvick y /data) sí es lo mismo. Pero es algo que suele fallar cuando de permisos se trata. Si tienes que ir más allá, no es que necesites otro programa, es que debes hackear tu móvil (tu o un amigo, vaya) para convertirlo en ROOT, flashear el RECOVERY y desde él instalar una Custom ROM.
Si nunca te has metido en el "oscuro" mundo del rooteo (y ahí no hay aplicaciones que valgan) no te recomiendo que lo hagas sin ayuda. Aunque todo tiene solución (al menos para mi), si no sabes llegar a ella puedes convertir tu móvil en un bonito ladrillo. Yo te doy la solución, pero no te animo a intentarla si no sabes dónde tocas.
Para que sepas de lo que hablo, ésta es una imagen de lo que es el RECOVERY (en este caso, ClockWorkMod), que funciona fuera de Android, es decir, antes de "encenderse"

Sólo desde aquí (o mediante Flashboot en tu PC, que tampoco es lo más sencillo del mundo a usar) puedes formatear tu móvil y darle permisos de ROOT

Gracias de nuevo Experto,

Entonces para que se limpie correctamente el sistema  al estar roteado no es suficiente un restaurado de fabrica desde el celular sino que tengo que formatearlo desde el ordenador no es así?

Olvide preguntarte si al formatear se pierde la liberación del móvil (para usar cualquier compañía) y si la contraseña sigue intacta gracias de nuevo