Came across that one the other day, after a kernel update someone trying to clean up the unused kernels actually managed to remove the current one.
Required for fixing the issue:
1. CD/DVD with the Distro that is on the server (this case Ubuntu server though I believe it would work the same way for Debain and other Debian based ones)
2. CD/DVD drive (well duh! 😀 )
Boot from the CD/DVD and enter the rescue mode.
Mount the /, /dev, /proc, /sys partitions, if not already done by the rescue wizard. If you had software raid you might need to assemble that one, got some info on how to here
Once that is mounted somewhere, chroot into the directory: (assuming mounted under /mnt/sysimage
And install the generic kernel
Reboot and remove the CD and this should allow you to boot the server up.