FOM does not protect against petrified status.
FOM clearly makes you immune to movement speed penalties of any kind, plus the specific states of paralyzed and restrained. Unless the flesh to stone does not clearly set the final state as either paralyzed or restrained, but sets the state as petrified, as it does, then FOM does only protects against the restrained effect. If you fail 3 saving throws you become petrified, regardless of the restrained effect you are immune to. You will not suffer any restrained effects, but you finally got petrified after failing 3 saving throws.
If we accept that petrification is not possible because it sets/reduces speed to 0, then we must also accept that FOM protects against all states that set speed to 0, e.g. Power Word Stun. So without FOM specifically specifying immunity to the Stunned condition together with Paralyzed and Restrained, also makes immune to being Stunned. If so, then why does it mention the Paralyzed and Restrained conditions? As examples?
Why "flesh to stone requires that the affected creature first be restrained before it is petrified" is not true:
It is stated that: "A creature restrained by this spell..." which is translated as "requires that the affected creature first be restrained". However the word "restrained" is poorly used here as it leads to this assumption. It should be better described as "A creature under this spell..." or "A creature targeted by this spell...". This is simply because the entire second paragraph makes no sense at all if we accept that "A creature restrained by this spell..." absolutely means "requires that the affected creature first be restrained".
This paragraph is quite clear:
You attempt to turn one creature that you can see within range into stone. If the target's body is made of flesh, the creature must make a Constitution saving throw. On a failed save, it is restrained as its flesh begins to harden. On a successful save, the creature isn't affected.
So we have 2 outcomes: you either pass or fail the saving throw, thus:
If you pass, you are not restrained, thus you do not need to roll because paragraph 2 begins with "A creature restrained by this spell..", but you are not that creature.
If you fail, paragraph 2 is relevant and valid. And if you fail the save 3 times total, then and only then are you petrified, because each failure makes you restrained and allows you paragraph 2 to be valid.
But if you fail, fail, and then pass, then paragraph 2 is invalid, because you are not the restrained creature, thus you do not roll!
So why does paragraph 2 state "The successes and failures don't need to be consecutive" as long as the very first passed saving throw halts the progress? Why does it require a total of 3 failures or successes to petrify you or end the spell if even the first saving throw success (pass) ends the spell?
It should simply state that if you fail the saving throw 3 consecutive times then you are petrified, else the spell ends at the first saving throw success.