Thanks for the reply. Mine is actually making it through the scanning/scoring, etc. all the way to the Outgoing queue. Looks like it is trying to get out, then I get the SMTP unavailable message.
I have also installed Webmin to more easily manage Postfix and can see the messages stuck in there. Forcing a release (postqueue -f) generates the same error.
Other mail, like from the cron jobs out to another Internet mailbox are working, which makes this even more strange.
I had previously followed the 8.04 Ubuntu Howto which had several issues, but I did get that one to release the mail. My next step here is to go through the configuration settings from that one and see what is different...