As chances são de que seu laptop suporta pae, mas ele não aparece. Tente instalar o pacote fake-pae:
sudo add-add-repository ppa:prof7bit/fake-pae && sudo apt-get update && sudo apt-get install fake-pae
após a reinicialização, cat /proc/cpuinfo
listará 36 bits physical
. Você pode então instalar novos kernels somente pae ou atualizar para uma nova versão do Ubuntu.
Eu tive o mesmo no meu laptop Pentium M e funcionou. Fiquei muito feliz, porque o laptop ainda estava funcionando bem e ainda é capaz de rodar a última versão completa do Ubuntu. Boa sorte!
(Não remova os kernels antigos ainda, porque se o seu laptop não suporta pae, o kernel pae-only entrará em pânico. Nesse caso, você pode inicializar o kernel antigo com o grub.)
(Se o falso-pae não funcionar no seu laptop, aconselho usar o Ubuntu 12.04 LTS, que é suportado até abril de 2017).