Mapping a function on the values of a map in Clojure

You can use the clojure.algo.generic.functor/fmap:

user=> (use '[clojure.algo.generic.functor :only (fmap)])
nil
user=> (fmap inc {:a 1 :b 3 :c 5})
{:a 2, :b 4, :c 6}

I like your reduce version just fine. I think it's idiomatic. Here's a version using list comprehension anyways.

(defn foo [m f]
  (into {} (for [[k v] m] [k (f v)])))