After you installed Ubuntu Server from the CD inside a VirtualBox you will get the following error:
PANIC: CPU too old for this kernel.
This is because Ubuntu Server has been compiled with PAE support, but this feature is missing in VirtualBox.
Solution is to change the "linux-server" kernel for a simpler one like "linux-i386".
1. Boot from Ubuntu Server CD and select "Rescue a broken system"
2. When it's asking about the device to use as root select the partition where the / filesystem is, in my case is /dev/sda1.
3. Now select "Execute a shell in /dev/sda1" and you get the linux prompt.
4. (Optional) If you have a system with multiple partitions you need to mount them with commands like from an alternative console, use ALT-F2 keys:
# mount /dev/sda2 /target/boot
# mount /dev/sda4 /target/var
This is especially important if you use a separate partition for /boot.
5. Now change the kernel with the following commands:
# apt-get update
# apt-get install linux-386
# apt-get remove linux-server
6. Now type
exit and reboot the system.