Woodhead of Fyvie in Aberdeenshire also has a church that is dedicated to All Saints.
Roadside of Catterline , also in Aberdeenshire (a few mile north of Inverbervie) is a similar instance of this way of constructing place-names: a tiny settlement [as here, Woodhead / Roadside], a short way removed from a bigger and more prominent one [Fyvie / Catterline]; with the word "of", intervening.
(The Scots seem to like, place-names-wise, this "A of B" formula -- it crops up all over Scotland, in various "forms and contexts"; of which the "little place 'of' big place", as above, is just one.)