Instalar o kernel do PAE é apenas parte dele - você também precisa atualizar o grub. Tente executar
sudo update-grub
e reinicie para ver se os kernels PAE aparecem no menu grub.
Como alternativa, você pode reinstalar com o lançamento de 64 bits. Eu também notei que o 3.4.0 não é um lançamento normal do kernel para 12.04. Deve ser 3.2.0-31-generic-pae
Os kernels genéricos normais foram removidos do Ubuntu 12.04 algum tempo após o lançamento inicial - os kernels pae agora são o padrão. Os kernels genéricos ainda são usados para alguns lançamentos, como o Lubuntu.