I have the same problem. The mail server gets the info from the php mail( function but the mail server rejects it because of the new AUTH restrictions.
Until there is a way to include AUTH in the header it looks like php might not be the best solution.
Actual mail server log:
[03/Nov/2001:12:35:40 -0900] SMTPD [xx.xx.xx.xx]: Mail relay attempt denied (not local, no AUTH).
[03/Nov/2001:12:35:40 -0900] SMTPD [xx.xx.xx.xx]: Invalid RCPT To: recipient, terminating.