Eu vi bios defeituosos causando problemas semelhantes.
Qual é a marca / modelo do computador?
Questão semelhante com resposta
Eventualmente, no caso do M6600 da Dell, a Dell lançou uma atualização do BIOS para corrigir o problema. Mas a solução alternativa do switch grub mencionada no link acima pode resolver seu problema.