2 errori fondamentali che quasi sicuramente riguardano il tuo problema:

nella query
Codice PHP:
$edit_contacts_query = mysql_query("UPDATE contatti SET indirizzo='$new_indirizzo', telefono='$new_telefono', cellulare='$new_cellulare', fax='$new_fax', email='$new_email'"); 
se la lasci così com'è farà questa modifica a TUTTE le righe della tabella.

se vuoi che cambi invece una determinata riga dovrei modificare la query
Codice PHP:
$edit_contacts_query = mysql_query("UPDATE contatti SET indirizzo='$new_indirizzo', telefono='$new_telefono', cellulare='$new_cellulare', fax='$new_fax', email='$new_email' where nome_campo_identificativo='valore:identificativo'"); 
secondo:

nell'action del form metti a dove deve puntare il form!!

Codice PHP:
echo "<table>
<form name=\"edit_contacts\" method=\"post\" action=\"tuapagina.php\">
<tr><td>Indirizzo:</td><td><textarea rows=\"3\" cols=\"20\" name=\"indirizzo\">".$contacts['indirizzo']."</textarea></td></tr>
<tr><td>Telefono:</td><td><input name=\"telefono\" type=\"text\" value=\"".$contacts['telefono']."\"></td></tr>
<tr><td>Cellulare:</td><td><input name=\"cellulare\" type=\"text\" value=\"".$contacts['cellulare']."\"></td></tr>
<tr><td>Fax:</td><td><input name=\"fax\" type=\"text\" value=\"".$contacts['fax']."\"></td></tr>
<tr><td>Email:</td><td><input name=\"email\" type=\"text\" value=\"".$contacts['email']."\"></td></tr>
<tr><td><input type=\"submit\" name=\"edit_contacts\" value=\"Edit\"></td>
</form>
</tr>
</table>";