Secondo me potresti fare cosi:

newsletter.php
Codice PHP:
<?php
session_start();
include("../config/config.inc.php");
?>

<html>
<head>
<title>Untitled Document</title>
</head>
<body>
<form name="newsletter" action="checkNewsletter.php" method="post">
<table width="100%" border="0">
    <tr>
        <td>

            <table width="45%" border="0" align="center" cellpadding="8" cellspacing="0">
                <tr>
                    <td>Oggetto</td>
                </tr>
                <tr>
                    <td> <input type="text" name="oggetto" size="65"> </td>
                </tr>
                <tr>
                    <td>Testo</td>
                </tr>
                <tr>
                    <td><textarea name="testo" cols="60" rows="10"></textarea></td>
                </tr>
                <tr>
                    <td>
                        <?php
                        $oggetto=$_POST['oggetto'];
                        $testo=$_POST['testo'];
                        
                        $query ="SELECT mail FROM utenti ORDER BY mail ASC";
                        $risultato = mysql_query($query);
                        $n_mail = mysql_num_rows($result);
                        $i = 1;
                        while ($row = mysql_fetch_array($risultato))
                        {
                            echo $row['mail'] . "<input type=checkbox name=check".$i.">
\n";
                            $i++;
                        }
                        ?>
                        <input type="hidden" name="n_mail" value="<?php print($n_mail); ?>">
                    </td>
                </tr>
                <tr>
                    <td><input type="submit" name="submit" value="Procedi" action="checkNewsletter.php"></td>
                </tr>
            </table>
            
        </td>
    </tr>
</table>
</form>
</body>
</html>
checkNewsletter.php
Codice PHP:
<?php
session_start();
include("../config/config.inc.php");

$oggetto=$_POST['oggetto'];
$testo=$_POST['testo'];
$n_mail = $_POST['n_mail'];

for($i=1;$i<=$n_mail;$i++)
{
    $mail = $_POST['check'.$i];
    mail($mail, $oggetto, $testo);
}

?>
Cosi dovrebbe fare esattamente quello che vuoi tu.
Se non capisci qualcosa sai dove trovarmi^^