I have a dual-core computer, and have been able to take advantage of both cores with Ubuntu for quite some time. At one point, I think when I upgraded to Gutsy, it stopped. It took a long time to figure out why... most of the pages the Google brings up refer to an older version, and they all tell you to install the -smp versions of the kernel. But Gutsy no longer has those.
There was one page that has the trick you need, but it's way at the bottom, so I'm writing it up here.
Here's the trick: the -generic versions of the kernel are the ones that support SMP. The -386 do not.
To fix it, you need to do two things. First, you need to run
apt-get install linux-generic
This gets the generic kernel on your system, and makes sure it stays up to date when things get upgraded. Chances are it's already there. Next, you have to edit your /boot/grub/menu.lst file to make sure it will boot from the generic kernel and not the 386 kernel. The grub program will put the 386 kernels ahead of the generic ones in the boot list. On my system, once I verified that the generic kernel would boot, I deleted all the 386 kernels. That should show them! I also had to remove and reinstall the linux-restricted-modules to get the nvidia drivers working again.