Sou completo novato no linux, mas tive uma experiencia como a sua e consegui resolver de uma maneira que gostaria de compartilhar. Caso sirva...
Como ele começou a demorar para aparecer a tela de desligamento (mais de um minuto) após eu tentar instalar um Gnome Power Maneger que eu baixei de um site que nem me lembro, decidi baixar do site oficial. Baixei, compilei e intalei. Pronto! voltou a funcionar normalmente.
Claro que antes de fazer disso, tentei desinstalar o Gnome Power Manager dentro do Synaptic... Mas não adiantou. Caso queira tentar, tome cuidado, pois quando vc pede pra desistalar o G.P.M. ele desinstala o Gnome Eviroment... Se vc reiniciar, ele não entrará no ambiente gráfico novamnte, pois estará desinstalado... aí vc teria que intalar pelo aptget...
Espero q resolva...
Boa sorte