Descobri que o problema de instalação do grub "o pacote grub-pc falhou ao instalar" para o Ubuntu 12.04.1 Server estava relacionado ao grau de acesso à rede. Se não houve conexão de rede (cabo desconectado) Grub-PC instalado OK (mas você precisa configurar a rede manualmente). Se estiver conectado a uma rede isolada ou limitada (acesso somente à LAN ou DNS inválido) que não pôde contatar um servidor externo do Ubuntu, a instalação do Grub-PC falhou. Somente se tivesse acesso total à rede, o Grub-PC conseguiria instalar corretamente, incluindo a rede.
Então, minha sugestão é primeiro solucionar problemas da sua rede local para garantir que ela forneça acesso completo à Internet. Se não estiver, corrija-o ou desconecte-se completamente da rede, faça a instalação e, em seguida, instale e solucione problemas na rede após a conclusão da instalação.