Here's what I had to do to get everything working on 64-bit Ubuntu 9.04.
First, the Palm Pre emulator requires VirtualBox 2.2+. If you're already running version 1.x, included in the Ubuntu repos, uninstall it.
$ sudo apt-get remove virtualboxDownload and install the latest 64-bit version of VirtualBox from virtualbox.org. I found a debian package for version 3.0 here.
If you're upgrading from VirtualBox 1.x, you'll need to convert your settings.
$ VirtualBox --convertSettingsNext, you'll need to download and install the mojo and novacom packages as noted in Palm's setup instructions.
But wait, what's this? There are only 32-bit packages available! What should we do? Luckily, someone has already run into the problem. Read this excellent post from the "Tried It" blog here, and apply the author's script to both the mojo and novacom packages. At that point, they'll install successfully.
Now, you can finish following Palm's installation instructions. It's time to start buildin' apps!