Mi idea seria que si existe OR el codigo sea asi:
Código PHP:
$query = ("SELECT user,mail FROM users WHERE user='$user' OR mail='$mail'");
$result = mysql_query($query);
if(mysql_num_rows($result) >= 1) {
echo"El mail o usuario ya estan registrados..";
}