Pokud máš v počítači graf. kartu od ATI a nainstalovaný proprietární ovladač fglrx, tak je to zřejmě opět problém mezi ovladačem, Xorg atd.
Je dobré vyzkoušet vypnutí z konzoly přes "sudo shutdown -h now". Pokud projde, tak by to mohl být ten problém, jak jsem psal. Zatím jsem nikde nenašel řešení, než dojde k opravě vypínám a restartuju počítač přes ikony na ploše, které spouští shutdown a reboot.
edit: Á, tak teď čtu, že ti to nejde ani přes konzoli, tak to může být něco jiného.