vps - How do I upgrade from linux kernel 2.6.33.5-rscloud

I have a VPS, which used to be on Slicehost and now Rackspace and it's running kernel 2.6.33.5-rscloud with Ubuntu 14.04.1 LTS. It seems I can't update my packages without getting onto a more recent kernel.

I've been trying various kernels and they all halt at startup, with different error messages. My menu.lst clearly controls which kernel I boot and I can change the default, watch it fail, and the change it back to zero in rescue mode.

/boot/grub/menu.lst
default     0
title    Ubuntu 14.04.1 LTS, kernel 2.6.33.5-rscloud
root     (hd0,0)
kernel   /boot/vmlinuz-2.6.33.5-rscloud root=/dev/sda1 ro quiet splash console=xvc0 selinux=0
initrd   /boot/initrd.img-2.6.33.5-rscloud
title    Ubuntu 14.04.1 LTS, kernel 3.16.0-77-generic
root     (hd0,0)
kernel   /boot/vmlinuz-3.16.0-77-generic root=/dev/sda1 ro quiet splash console=xvc0 selinux=0
initrd   /boot/initrd.img-3.16.0-77-generic
title    Ubuntu 14.04.1 LTS, kernel 4.4.0-116-generic
root     (hd0,0)
kernel   /boot/vmlinuz-4.4.0-116-generic root=/dev/sda1 ro quiet splash console=xvc0 selinux=0
initrd   /boot/initrd.img-4.4.0-116-generic

I've been playing with grub, grub2, pvgrub without success. I've had issues not finding the boot device (disable UUID) and problems with the realtime clock in the later kernels. I'd prefer not to build a new server from scratch as I have many services running well and various DNS services pointing to its IP.