Isso pode ser devido ao carregamento de uma versão incorreta da imagem do kernel do Linux para uma versão do Ubuntu.
Tente remover manualmente qualquer imagem indesejada do kernel do Linux do diretório / boot e faça o 'update-grub' e reinicialize a sua máquina.
No meu caso, instalei pela primeira vez o 32bit-Ubuntu-11.10, que armazenava a imagem do Kernel 3.0.0-14 no diretório / boot. Mais tarde eu instalei o 64bit-Ubuntu-11.10, que precisava da imagem do kernel 3.0.0-12. Mas o grub selecionou a versão errada do kernel 3.0.0-14, que é configurada para a CPU de 32 bits para inicializar o Ubuntu 11.10 de 64 bits.
Assim que eu removi as imagens do kernel do 3.0.0-14 e atualizei o grub, obtive boot bem-sucedido todas as vezes. Apenas tente.