Cultist description says that any regions adjacent to cuthullu (even due to special powers) are one cheaper. Now flying mat gives flying, which kinda allows treating any territory as adjacent (not sure about exect wording, played at friends). I would assume that attack using flying mat would get discount. Though everyone opposed that, I had to attack with normal cost. Still I wonder what other think? Rules are not terribly clear on this part, IMO.
From a literal reading of the rules, I believe your friends were correct; you do not get the discount when attacking a non-adjacent space with Flying Doormat.
The Cultist rule says:
Conquer any region adjacent to the Great Ancient (this includes any Region that may be adjacent as a result of any Racial, Special Power, Popular Place or Righteous Relic you may control) at 1 less Cultist token than usual.
The Flying Doormat rule:
Once per turn, the player whose troops control the Flying Doormat may conquer any Region, even one that is not adjacent to his.
The Flying Doormat does not make things actually adjacent, or treated as adjacent. Rather it allows you to conquer a space that is "not adjacent." Compare this to the wording on The Great Brass Pipe:
All Regions of the same Terrain type as the one in which the Great Brass Pipe is discovered are considered adjacent, for the player's whose Troops occupy that Region.
So the Cultist's ability would work with the Great Brass Pipe, because those spaces are considered adjacent, but for the Flying Doormat, the spaces are not considered adjacent.
I agree with you that the rules are a little confusing on this. Especially since the Cultist's rule states that Righteous Relics you control do apply, and yet there is no Righteous Relic in the game that makes non-adjacent spaces adjacent! This is definitely misleading; either Flying Doormat was intended to work differently than the way they worded it, or they just wrote the Cultist's rule without considering the full list of Righteous Relics that actually exist in the game. That rule also would allow for expansions to include new Righteous Relics that work with the Cultists.
The rule book online: http://cdn0.daysofwonder.com/smallworld/en/img/su_rules_en.pdf