Do you really expect Microsoft to make it easy installing something like Linux? Take my advice and dump VirtualPC 2004. Install VMware Server instead because it works better with Linux.
BTW, Ubuntu Edgy doesn't play nice in VMware. You should use Dapper for now. Basically the VMtools don't work properly with Upstart (Ubuntu new replacement for the init system).
If you're new to linux I will suggest running it on a liveCD. No installation and no virtual machines. This will also let you test your raw hardware with linux rather than virtual hardware through a virtual machine. That way you will know what will work and what won't. Using a liveCD gives you an almost identical experience to installing it (full install, not virtual) other than performance.