bem, parece que o problema é a versão do kernel.
A última atualização do kernel foi 3.5.0-27 e parece que tem alguns problemas com os drivers de vídeo de várias placas gráficas. Depois de ler este dois relatórios de bugs achei que o kernel poderia ser o problema e tente inicializar com o 3.5.0-26 (valeu bem que o ubuntu armazene os últimos kernels usados apenas no caso), não há problema desde então. Eu consegui inicializar meu laptop 10 vezes a partir de 10 tentativas, então acho que o problema era o kernel.
Eu não sei exatamente qual foi o problema e os relatórios de bugs ainda não foram resolvidos, então até lá não atualizarei meu sistema para a versão do kernel 3.5.0-27.
Obrigado pelas suas respostas