I've noticed lengthy slowdowns before while ac-nrepl is 'caching JVM class names', but recently found a show-stopper where this hangs indefinitely (I just left it overnight) after adding "(use 'clj-stacktrace.repl)" to :repl-options :init in my .lein/profiles.clj.
Not sure whether this is ac-nrepl's fault or clj-stacktraces (so I opened mmcgrana/clj-stacktrace#18 too), but in general it might be good to put some kind of timeout or limits on this caching business, or do it in a separate thread (no idea if this is possible!) since it seems to block the emacs UI pretty severely with a killall emacs24 being the only way I found to interrupt it.
(If it's doing something recursive, perhaps it needs some recursion depth limit or cycle avoidance logic?)