Tente desligar usando o terminal executando:
shutdown -h now
e verifique a saída que ele fornece. Provavelmente você tem um daemon que, por algum motivo, está bloqueando o processo.
Desligar usando o modo de texto deve lhe dar algumas dicas.
Espero que isso ajude.