When I upgrade to Hardy Heron, it looks like I'll have an easier time getting mail to work.
Here is an Ubuntu-specific recipe that looks like it will do the job:
https://help.ubuntu.com/7.04/server/C/postfix.html