Credo sia perchè tu prima lo inserisci e poi controlli.
Riscrivi il codice tipo così (come impostazione):
<?php
$query_sel = "SELECT * FROM tabella_prova WHERE nome='$nome'";
$eseguisel = mysql_query($query_sel, $db);
$eseguiins = mysql_query($query, $db);

if (isset($_POST['nome'])) {
if ($eseguisel == TRUE){
echo "Esiste";
}else {
$query = "INSERT INTO tabella_prova (nome,cognome) VALUES '$nome', '$cognome')";
}

?>