> Here is the example.  This is essentially the example in the manual, but 
 > I have added an exception to the module:
 > 
 > module rec A : sig
 >    type t = Leaf of int | Node of ASet.t
 >    exception Fail
 >    val compare : t -> t -> int
 > end = struct
 >    type t = Leaf of int | Node of ASet.t
 >    exception Fail
 >    let rec compare = (* suitable definition *)
 > end
 > and ASet : Set.S with type elt = A.t = Set.Make(A)
 > 
 > Then we can try to use it:
 > 
 > # let x = A.Leaf(3);;
 > val x : A.t = A.Leaf 3
 > # let s = ASet.add x ASet.empty;;
 > val s : ASet.t = <abstr>
 > # let s' = ASet.add x s;;
 > Exception: Undefined_recursive_module ("recmodtest.ml", 6, 6).
 > 
 > If we remove the "exception Fail" from the signature, everything works 
 > just fine.  Is this behavior correct?  (I am using OCaml 3.08.1)

I think this is due to the necessary coercion between your A and the
OrderedType argument expected by Set.Make. Your code is compiled to
something like

module rec A : sig
   type t = Leaf of int | Node of ASet.t
   exception Fail
   val compare : t -> t -> int
end = struct
   type t = Leaf of int | Node of ASet.t
   exception Fail
   let rec compare = (* suitable definition *)
end
and ASet : Set.S with type elt = A.t = Set.Make(
  struct
    type t = A.t
    let compare = A.compare
  end)

According to the (brief) explanation in the manual, 

"Evaluation of a recursive module definition proceeds by building
initial values for the safe modules involved, binding all (functional)
values to fun x -> raise Undefined_recursive_module. The defining
module expressions are then evaluated, and the initial values for the
safe modules are replaced by the values thus computed."

Here, the argument passed to Set.Make is never replaced with a proper
value. If you explicit the coercion with some A' as below, the code
works. Is it all well this way, or did I miss something?

module rec A : sig
  type t = Leaf of int | Node of ASet.t
  exception Fail
  val compare: t -> t -> int
end
    = struct
      type t = Leaf of int | Node of ASet.t
      exception Fail
      let compare t1 t2 =
        match (t1, t2) with
          (Leaf s1, Leaf s2) -> Pervasives.compare s1 s2
        | (Leaf _, Node _) -> 1
        | (Node _, Leaf _) -> -1
        | (Node n1, Node n2) -> ASet.compare n1 n2
    end
and A' : Set.OrderedType with type t = A.t = struct 
    type t = A.t
    let compare = A.compare
  end   
and ASet : Set.S with type elt = A'.t
      = Set.Make(A')

let x = A.Leaf(3)
let s = ASet.add x ASet.empty
let s' = ASet.add x s