Como seria difícil fazer backup de seus dados e fazer outra instalação limpa? Parece que algo está corrompido na sua instalação, o que pode explicar o comportamento de inicialização não-determinístico. Além disso, qual modelo de computador você tem? Ajudaria a conhecer mais detalhes do seu computador, instalação e ambiente.
Eu sei que quando eu instalei o Ubuntu 12.04 no meu Macbook Pro 5,2 eu tive alguns problemas de boot simular. Eu simplesmente re-instalei com outra instalação limpa e tudo estava bem depois disso.