This is how I got Ubuntu 7.10 installed on my MacBook Pro running Parallels build 5582.
Start with the Ubuntu Alternate disc. NOT the Ubuntu Desktop or Server Disc!!
Setup a new virtual machine and make sure you pick 512 M for the amount of RAM. (There seems to be an issue when allocating larger amounts of memory, which will cause the VM will freeze on boot.)
Boot of the disc, and run through the installer. It will be the console based installer, not the fancy GUI installer, but it works just the same.
Towards the end of the installation you will be prompted to setup your xserver. Simply enter in the screen resolutions that you would like to have available.
I went into the System Preferences -> Display panel and just marked all of the resolutions that were listed there.
After the installer finishes, reboot, and you should be all set.
If you want, you can install the Parallels Tools. They will make the integration with the Mac OS a little nicer. I ran the provided installer, rebooted again, and everything worked fine.