Revisa tu consulta... puede ser que tengas algun error hay...
y quieres coloca parte del codigo a ver si te podemos ayudar..
Código PHP:
$consul = mysql_db_query($database,"SELECT CampoNombre, CampoApellido FROM TablaUsuario WHERE CampoNombre = '$nombre' AND CampoApellido = '$apellido'");
if($row = mysql_fetch_array($consul))
echo "Usuario $nombre $apellido ya Exite";
Que pena se me olvidaban la comillas de '$nombre' y las de '$apellido'