You'll get a different error message if relaying's denied, so you're not far enough along to know if that's going to be a problem or not.
You do have MailHost set up correctly in your nsd.tcl file. i.e. to 127.0.0.1? On my boxes I'm just using my ISP's smtp server rather than set up sendmail on my box, and have never had a problem getting it to work. If someone's listening on port 25 and expecting SMTP, as seems to be the case here, you should at least get a more specific error rather than the "there's no host" error.
