Lo solucioné!
Luego de buscar y no encontrar respuesta me puse a pensar qué cambios había hecho al sistema antes de reiniciar... Lo más "sospechoso" que había hecho fue desinstalar Evolution via Synaptic. Y ahí busque...
Resulta que este programa tiene unas dependencias de gnome y se ve que al desinstalar via synaptic, le di que vuele a todo
...estúpido, si, pero le había pasado a mas de uno.
Luego, tuve que quitar el entorno gráfico (no me acuerdo si era ALT F4 o algo así, soy novato), me loguee y puse el comando "
sudo apt-get install ubuntu-desktop" (o similar, lo puse de memoria) para instalar nuevamente esas librerías que quité.
Y.... listo!
Ojalá que de verdad le sirva a alguien, saludos!