Stai semplicemente sbagliando funzione. Sostituisci mysql_fetch_array con mysql_fetch_row, oppure aggiungi il secondo paramentro a mysql_fetch_array($result, MYSQL_ASSOC).
mysql_fetch_array senza secondo parametro ti conta sia i campi come indice numerico che come indice associativo (equivalente al secondo parametro MYSQL_BOTH), per cui ti conta doppio.
[PHP]
<?php //Dati connessione
$host = "localhost";
$user = "root";
$psw = "";
$database = "prova";
$conn = mysql_connect($host,$user,$psw) or die(mysql_error());
$db = mysql_select_db($database) or die(mysql_error());
$query = "SELECT * FROM utenti";
$result= mysql_query($query);
$array = mysql_fetch_array($result, MYSQL_ASSOC);
echo count($array);
echo '<pre>';
var_dump($array);
echo '</pre>';
mysql_close();
?>
[/PHP]
http://php.net/manual/it/function.mysql-fetch-array.php
Ma sarebbe più corretto
[PHP]
<?php //Dati connessione
$host = "localhost";
$user = "root";
$psw = "";
$database = "prova";
$conn = mysqli_connect($host,$user,$psw, $database) or die(mysqli_error($conn));
$query = "SELECT * FROM utenti";
$result= mysqli_query($conn, $query);
$array = mysqli_fetch_array($result, MYSQL_ASSOC);
echo count($array);
echo '<pre>';
var_dump($array);
echo '</pre>';
mysqli_close($conn);
var_dump($array);
?>
[/PHP]