I think I'm probably running into this, except that there seems to be some non-determinism involved.
It seems to behave differently, depending on whether I run it from within a deftest or from the REPL. (Running it from the REPL seems to fail every time. Running it inside deftest seems much more reliable).
My really long-winded description is at https://groups.google.com/forum/#!topic/clojure/zPWPmQGm94w
The sample where I tried to document exactly what I'm seeing is at https://gist.github.com/jimrthy/21851c52a8cd6b04a31ed08b1d0a7f04 (when I wrote that, running inside deftest seemed to work every time. That is not the case).
If nothing else, it would be nice to have better error messages that include the name of the spec it's failing to generate. Actually, that would be generally helpful and possibly worth its own ticket. Please let me know if you'd like me to create one.