Aas far as I understand Mux, r.Headers must specify one header value to match. See https://github.com/gorilla/mux/blob/master/route.go#L206 for an example.
If you want to match many header values, you should try r.HeadersRegexp. See https://github.com/gorilla/mux/blob/master/route.go#L231.