It is a genitive marker that is connecting two noun phrases. This is the typical, most common usage of the particle. You may interpret it as "A no B" meaning "A of B" or "A's B".
In this phrase, it is (sore nanoni) no ((iikae) ya (betu no iikata)), "a change in wording or another way of saying [the expression] 'sore nanoni'".
Note though the second -no. This is the same usage as the first, which you seem to not be having trouble with. It is poor style. The writer could have made it more clear by putting quotes such as 「」 around the sore nanoni.