esatto.. mi raccomando che <table> e </table> vanno fuori dal ciclo while! Se no ti crea tante tabelle quante sono i record del tuo db... 
Codice PHP:
$sql = "SELECT NOME,COGNOME,TELEFONO FROM rubrica";
$result = mysql_query($sql) or die ("Errore: " .mysql_error() );
echo "<table><tr><td>Nome</td><td>Cognome</td><td>Telefono</td></tr>"; // Questo stampa la prima riga con i nomi delle colonne
while($array = mysql_fetch_array($result))
{
print "<tr>"; //Apre la riga
print "<td>".$array['NOME']."</td>";
print "<td>".$array['COGNOME']."</td>";
print "<td>".$array['TELEFONO']."</td>";
print "</tr>"; //chiude la riga
}
echo "</table>";
giusto per essere completi ^_^