I'm trying to do this on a virtual server with Ubuntu 8.04. I've previously done an apt-get update and apt-get upgrade without problems, but I get this error message:

"Package postfix-tls is a virtual package provided by:
  postfix 2.5.1-2ubuntu1.2
You should explicitly select one to install.
E: Package postfix-tls has no installation candidate"

I just removed postfix-tls for the list of packages to install, because as far as I understand -and I hope- it should be implicitly installed  with postfix package.

It's a bit weird anyway, I've installed another Ubuntu 8.04 server with this guide before and I do not remember this problem. Maybe something has changed on 8.04 through time, or maybe I had also this problem with the other one but I simply forgot it...