Ever see that message? I got it in February when I put Ubuntu 7.10 Server Edition on my roommate's laptop. Jdong pointed me at a bug explaining the problem. I don't believe I ever mentioned it here, but I was just on the phone with a friend, and he said he had this weird problem where it said the CPU was wrong instead of booting. "CPU too old, you mean?" "Yeah, that's it" "Server Edition?" "Yep"
The reason it's doing this is that the -server kernel expects PAE, which lets PCI devices be mapped above the 4GiB line so if you have 4GiB, you can actually use all 4 instead of having your PCI devices be mem-mapped right over where your memory should go and right out of the range of what 32bit can handle.
To fix it, get out a live cd and chroot into the hard drive.
sudo chroot /dev/sda1, assuming first drive, first partition (change sda1 to whatever corresponds to your partition if this is not the case). Once in there, run
sudo apt-get install linux-image-386, or, if you have a dual-core processor (so you can get SMP),
sudo apt-get install linux-image-generic. Then, remove the -server kernel by entering
sudo apt-get remove linux-image-$(uname -r) in your terminal. After a reboot, it should, well, be able to boot.