user> clojure-version
{:major 1, :minor 4, :incremental 0, :qualifier "alpha1"}
user> (def x (keys (java.util.IdentityHashMap. {:a true :b true})))
#'user/x
user> x
(:b :a)
user> x
(:a :a)

As discussed on the mailing list, it's not clear exactly whose fault this is:
https://groups.google.com/group/clojure-dev/browse_frm/thread/bed458abf8e266aa#
given that the javadocs for iterators and entrySet dont' seem to require (or mention at all) whether each .next() must return a unique value.

keys and vals could be fixed by using keySet and values rather than entrySet, at least in this case, but this would not help for seq.