php mail stopped working for some addresses on debian

Question

My Debian Lenny server was happily sending mails from the php mail() function up until a few days ago. Now, it will return false for certain email addresses I have been using.

I pointed php to sendmail in php.ini but that didn't change much. I noticed when I run:
sudo /usr/sbin/sendmail -bv [email protected]
I get the message:
[email protected]... User unknown

But if I try with another address ([email protected]) I get:
[email protected]... deliverable: mailer esmtp, host example.com., user [email protected]

This is consistent with the result returned from php mail().

I've never set up any mail sever stuff on this server because I am a n00b. So any resources that will help me learn would be much appreciated.

Thanks