Você pode tentar baixar o arquivo .deb relevante de link e link :
wget http://launchpadlibrarian.net/79829520/linux-headers-2.6.32-34-generic-pae_2.6.32-34.77_i386.deb
wget http://launchpadlibrarian.net/79829514/linux-headers-2.6.32-34_2.6.32-34.77_all.deb
Em seguida, instale usando:
sudo dpkg --install linux-headers-2.6.32-34-generic-pae_2.6.32-34.77_i386.deb linux-headers-2.6.32-34_2.6.32-34.77_all.deb
Mas, a menos que haja uma razão específica pela qual você ainda esteja usando um kernel PAE antigo no 12.04, acho que seria melhor usar um kernel empacotado em 12.04. A atualização para o 12.04 deve ter instalado um kernel mais novo. Talvez você precise atualizar seu padrão do grub ou selecionar manualmente um kernel diferente durante a inicialização?