PAE significa Physical Address Extension, e é um recurso de CPU que foi adicionado aproximadamente na geração do Pentium III para lidar com grandes tamanhos de RAM. Apesar desse recurso ser parte da arquitetura P3, algumas CPUs de geração P3 e P4 suportam o recurso, mas relatam incorretamente que não o possuem. A primeira coisa a tentar é adicionar o parâmetro "forcepae" à linha de inicialização que o GRUB usa - isso pode resolver o problema para você.
Se isso não funcionar, você precisará encontrar uma versão do kernel não-PAE do Ubuntu ou mudar para outra distribuição que tenha versões não-PAE disponíveis (já usei com sucesso o antiX no Pentium 2 processadores, mas essa distro estava ficando um pouco longa no dente da última vez que eu olhei para ela).