Hace tiempo usaba un Kernel hecho por Linode y no tenía problemas para usar Lish (Linode Shell, por si no puedes conectar por SSH por algún problema).
Desde que cambié el Kernel en Linode Manager a pv-grub-x86-32 Lish dejó de funcionar, pero no lo relacionaba con esto porque desde el cambio hasta que intenté usar Lish pasó mucho tiempo.
La solución se encuentra en: http://www.linode.com/wiki/index.php/PV-GRUB#Boot_Configuration
En Debian Squeeze tuve que cambiar el /etc/inittab como indica en esa wiki (cambiando 0:2345:respawn:/sbin/getty 38400 tty1 por 0:2345:respawn:/sbin/getty 38400 hvc0) y deshabilitar Xenify Distro en el Linode Manager.