Problems with Mail on CentOS

Drupal 6 and now Drupal 7 are unable to send any form of mail from my server. I have read through many, many mail problems but none seemed to quite fit the description.

Here is my configuration:

Apache/2.2.15
CentOS 6.2
PHP 5.3.3

I am able to use both sendmail and php's mail function to send mail.

Whenever a user registers or I try to send myself a recovery email, I am given this fairly useless error:
Error sending e-mail (from exaple@mydomain.com to example2@someonesemail.com)

I have traced the code all the way to system.mail.inc where this code of block is being executed:

if (!isset($_SERVER['WINDIR']) && strpos($_SERVER['SERVER_SOFTWARE'], 'Win32') === FALSE) {
      if (isset($message['Return-Path']) && !ini_get('safe_mode')) {
        // On most non-Windows systems, the "-f" option to the sendmail command
        // is used to set the Return-Path. There is no space between -f and
        // the value of the return path.
        $mail_result = @mail(
          $message['to'],
          $mail_subject,
          $mail_body,
          $mail_headers,
          '-f' . $message['Return-Path']
        );
      }

Essentially the mail function is being called but not succeeding. I even tried sending a simpler mail, with less arguments (no success):

if (!isset($_SERVER['WINDIR']) && strpos($_SERVER['SERVER_SOFTWARE'], 'Win32') === FALSE) {
      if (isset($message['Return-Path']) && !ini_get('safe_mode')) {
        // On most non-Windows systems, the "-f" option to the sendmail command
        // is used to set the Return-Path. There is no space between -f and
        // the value of the return path.
        $mail_result = @mail('example2@someonesemail.com', 'My Subject', 'Hello World');
      }

As previously stated, this by itself works:

@mail('example2@someonesemail.com', 'My Subject', 'Hello World');

It's probably some type of configuration issue but I can't seem to track it down... Any help would truly be appreciated.

Thanks,

Arturo Aparicio