Ok, acabei de encontrar o mesmo problema no meu Z580 com o Ubuntu 12.04. Ele reiniciou bem algumas vezes e depois desligou na tela roxa. Eu tive que forçar a reiniciá-lo novamente, e agora ele só mostra um cursor piscando. Escolher a opção de inicialização de recuperação desliga no mesmo lugar que você descreveu.
Após algumas pesquisas, parece que este é um problema comum no Z580 recentemente, e parece que tem algo a ver com a inicialização do UEFI. Olhe para o seguinte dois threads . Infelizmente, ainda não há solução sólida.
Espero que esta informação ajude alguém mais experiente a encontrar uma solução.
ATUALIZAÇÃO:
Consegui resolver este problema inicializando no kernel anterior do Linux 3.2.0-29-generic (o que veio com o disco de instalação 12.04). Para inicializar usando um kernel anterior, escolha "versões anteriores do linux" no menu de inicialização do grub. Mais tarde, percebi que o problema realmente ocorre após uma atualização do kernel para a versão 3.2.0-35-generric. Portanto, ele ainda não inicializa no novo kernel e trava como descrito na pergunta original. Então, eu acredito que isso tenha algo a ver com o novo kernel 3.2.0-35-.