I was having a problem with FC4 becase SELinux was enabled and preventing a php webapp in apache from sending email.

The log in /var/log/messages was reporting:

avc: denied { write } for pid=6608 exe=/usr/sbin/sendmail.sendmail name=clientmqueue
dev=dm-0 ino=2343033 scontext=user_u:system_r:system_mail_t
tcontext=system_u:object_r:var_spool_t tclass=dir

I didn't want to disable SELinux as this was a external facing machine, but fortunately I was able to find a fix for this problem here

To summarize, the following command fixed the problem for me.:

rpm -q -l sendmail | /sbin/restorecon -R -f -