Sooooo ... depois de um dia pesquisando, encontrei o problema.
Eu não sei porque ou como, mas houve um bug no script init do gdm. Eu não tenho ideia de como chegou lá.
A maneira que eu encontrei foi tentando reiniciá-lo manualmente, fazendo sudo /etc/init.d/gdm restart
Então ele disse que havia algo errado em uma linha e eu o removi.
Ele começa agora, não apenas na inicialização. vai olhar para isso mais tarde, pelo menos eu posso trabalhar agora.