Grub: No setup signature found

When you upgrade from 2.6.22 to 2.6.23 grub 0.97 is required. Although most distribution will install this grub version, chances are high you will find under /boot/grub old files (in my case 2004/2005) and hence the setup of grub did not run.

Have a look at http://www.gnu.org/software/grub/manual/html_node/Installing-GRUB-natively.html to re-install grub and make sure to have a distribution recovery image in case it goes wrong.