For those of you playing along at home, this is because of Clojure's reducers framework [1]. If we were to extend 'clojure.core.protocols.CollReduce' to ArrayList, we'd get similar performance, but the important point is that efficient iteration across immutable collections is very much possible.
http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo...
EDIT: and my response is just a little redundant now