For fun, a solution with zip:

class Hash
  def map_keys &block
    Hash[ * keys.map(&block).zip(values) ]
  end
end

Clay