The default text console on Ubuntu 10.04 uses a graphical mode that uses a planar memory layout. Apparently this graphics mode is extremely hard to virtualize efficiently.
Setting another (graphical) text mode that is fast, even on virtualized machines, is actually not that hard. You need to edit the file /etc/default/grub, change the GRUB_GFXMODE setting to something like 800x600 or 1024x768. The vbeinfo command, available from the grub command line, can tell you what modes your hardware supports. To actually get to the grub command line you need to press and hold the Shift key while booting the VM to activate the menu, and then press the C key to get a command line.
To rebuild /boot/grub/grub.cfg, which is Grub's configuration file, you need to run the command update-grub2. Always remember to do this after you make a change to /etc/default/grub or any file in /etc/grub.d/.
Unfortunately, doing this will only change the mode for Grub. To have your text consoles in the same mode you need to hack the file /etc/grub.d/00_header a little bit. After the line that looks like this,
you need to insert another line that looks like this,
This should ensure that the Grub graphical mode you specify in /etc/default/grub is kept throughout the boot process.
The last step is to remember to re-run update-grub2 to re-create /boot/grub/grub.cfg and then reboot and enjoy fast text consoles.
UPDATE: I've noticed that /etc/grub.d/10_linux sets gfxpayload if you specify its parameter in the GRUB_GFXPAYLOAD_LINUX variable in /etc/default/grub. This should avoid having to manually edit any non-configuration files. My /etc/default/grub config file now only contains this mode information: