Since I have > 3GB of RAM, I installed linux-image-generic-pae so that I could access up to 16GB on my Karmic Koala install. Note that installing a new kernel doesn't choose it as the default in grub (which is actually now grub2). So in /etc/default/grub I set GRUB_DEFAULT=saved so that it'd remember my choice, and then rebooted and hit SHIFT during the (very brief) grub blip to pull up the menu and choose the new kernel, which it then remembers.
Unfortunately, that broke my nvidia driver: when I rebooted into the kernel, the text login screen just flickered as xorg restarted constantly. This is due to 2 bugs:
Summary: I had to
apt-get remove --purge linux-headers-2.6.31-15
And then, when I did an
apt-get install linux-headers-2.6.31-15-pae
it automatically rebuilt (successfully) the nvidia.ko.