From Installing Ubuntu 9.04 on Virtual PC 2007 SP1

Boot Ubuntu 9.04 up. On the first screen, choose [English].
Then press [F4] and select [Safe Graphics].
Then press [F6], but do not select any option. Instead press [Escape] and it will allow you to change the command line. Remove the option "quiet splash --" and replace it with "vga=791 noreplace-paravirt" instead.
Press [Enter] to start the installation.

I had to use a lower resolution to get it to work.

vga=788 noreplace-paravirt xforcevesa noacpi

https://help.ubuntu.com/community/BootOptions

http://en.wikipedia.org/wiki/VESA_BIOS_Extensions#Linux_video_mode_numbers

VM Additions are at

http://www.microsoft.com/downloads/details.aspx?FamilyID=bf12642f-77dc-4d45-ae4e-e1b05e0a2674&DisplayLang=en