prewalk-replace is slightly simpler than @mobyte's answer if you're strictly swapping one value for another:
(def thing '( (a b) f ( (a b c) (e r) a ) a ))
(use '[clojure.walk :only [prewalk-replace]])
(prewalk-replace {'a 'z} thing)
; ((z b) f ((z b c) (e r) z) z