Teve um problema semelhante, enquanto 12.04 estava em beta. Agora foi embora. Minha recomendação é garantir que você instale a atualização mais recente do kernel (ou seja, certifique-se de que seu sistema está 100% atualizado) e tente reinstalar seus drivers de vídeo (se eles forem proprietários ou de outra forma instalados automaticamente). Eu tive problemas com a inicialização quando eu não reinstalar meus drivers ATI após uma atualização do kernel, embora eu tenha certeza que eles não causariam um problema ao desligar.
Se isso não funcionar, talvez você queira verificar se há algo nos registros do sistema, embora não tenha certeza de quais seriam aplicáveis.