I realize this thread is marked 'SOLVED' so this is a FWIW...

I ran into a similar issue on an old HP Compaq (w/Celeron cpu) laptop with almost identical spec as the OP's Celeron laptop. This HP laptop I type of is running 32-bit LM13, (i.e. Ubuntu 12.04 LTS) and I was attempting to upgrade the kernel to linux-image-generic-lts-quantal 3.5 but as posted above installs failed with the 'non-PAE CPU' error. Then I found the solution for my issue here:

http://askubuntu.com/questions/20398.../256037#256037

Install the 'fake-pae' repository, install 'fake-pae' package, then do another install/re-install of the 3.5 kernel packages, reboot.
.