Eu realmente não tenho certeza se isso tem algo relevante a ver com a sua situação, mas imaginei que contribuiria com uma orientação para perseguir de qualquer maneira, já que sua pergunta ainda não teve nenhum outro sucesso.
Acabei de instalar o 12.04.4 fresh (sem atualização da versão anterior) e não tive nenhum problema ao instalar o freeglut3-dev com o apt-get, como você tentou sem sucesso. Você diz no seu OP que você segue as instruções para a instalação em uma nova instalação do Ubuntu 12.04.3, mas não especifique se você tem uma nova instalação ou atualizou de uma versão anterior.
Dito isto, desde a minha nova instalação eu instalei uma série de bibliotecas relacionadas, já que eu também estou no processo de executar o CUDA. Talvez algo que eu tenha desencadeado uma série de pacotes a serem instalados resolva esse problema de maneira proativa. Eu quebrei e consertei o ubuntu-desktop, a unidade e compiz algumas vezes no processo, então muita coisa aconteceu.
No entanto, no meu mexer a seguinte informação ligada apareceu em descobrir exatamente quais são as diferenças em 12.04.4 de 12.04 versões anteriores. Relaciona-se com alguns componentes opcionais que você pode ou não ter em sua instalação atual, dependendo de como você chegou em 12.04. 4
Não tenho certeza se isso vai ajudar ou atrapalhar, mas vale a pena ler tudo de qualquer maneira.
EDIT: Informações adicionais podem ser encontradas aqui link nos primeiros parágrafos. Isto é predominantemente relacionado a uma fonte ppa para os drivers nvidia mais recentes, ao invés de instalar a partir de pacotes .run, mas contém algumas outras informações potencialmente relevantes.
Em resumo, gostaria de saber se o seu problema está relacionado ao fato de que novas instalações do 12.04.4 possuem pilhas backport Precise X, o que eu entendo é um componente opcional do upgrade para o 12.04.4 de um release antigo, como discutido no primeiro link que postei.
Em outras palavras, talvez o seu problema esteja relacionado à versão do kernel vs. versão da mesa. Talvez tente um gerenciador de pacotes melhor, como o synaptic, para ver qual versão dos pacotes da tabela está sendo alimentada em seu sistema, da qual depende o freeglut3-dev. Meus pacotes de mesa são 8.0.4-0ubuntu0.7 e estou executando o kernel 3.11.0-17-generic.