PHP - Ayuda con la función mail

Hola a todos:
Tengo un problema que no consigo resolver. Estoy implementando un sistema de envío de mails para los registrados de mi web. Mi servidor tiene su SMTP y me dice que el php.ini ya está configurado ya que algunos alojados ya hacen mailing sin problema alguno.
A mí me da el siguiente error:

PHP Warning: mail() [function.mail]: Failed to connect to mailserver at "localhost" port 25, verify your "SMTP" and "smtp_port" setting in php.ini or use ini_set() in ...

El script es el siguiente:

<?php

set_time_limit(900);
include("connect.php");
$id = preg_replace("/'/<>"/","",$_GET['id']);
if (empty($id))
die("Invalid ID");
$link = "SELECT * FROM newsletters WHERE id='$id'";
$res = mysql_query($link) or die(mysql_error());
$r = mysql_fetch_assoc($res);
$subject = $r['name'];
$message = $r['content'];

$headers = 'MIME-Version: 1.0' . " ";
$headers .= 'Content-type: text/html; charset=iso-8859-1' . " ";
$headers .= 'From: newsletter@' . $_SERVER['SERVER_NAME'] . " " .
'Reply-To: newsletter@' . $_SERVER['SERVER_NAME'] . " " .
'X-Mailer: PHP/' . phpversion();

$link = "SELECT * FROM users WHERE status='subscribed'";
$res = mysql_query($link) or die(mysql_error());
while ($r = mysql_fetch_row($res))
{
$email = $r['email'];
$mail = mail($email, $subject, $message, $headers);
}
?>

¿Aguna sugerencia?

P.D.: Un desesperado.