Ah...I run redhat 7.2 and was having a similar problem. I had it setup correctly in the php.ini according to the documentation, but none of my mail functions in PHP worked. I finally tired of it and hacked together a couple functions to parse headers and recipients and send mail and packaged it up as a php include file. It works quite well. Let me know if you need it.
EDIT: nope...not the same problem...my box is it's own smtp server...doesn't run through the ISP's
EDIT again:
Here is that .inc file. To be honest, I snagged it from somewhere else on the net and modified it to meet my own needs, so I can't take credit for it. It does work quite well.