Based on how the paragraph is written, I would say the first failure does not count.
Let’s break it down:
A creature restrained by this spell must make another Constitution saving throw at the end of each of its turns.
This only affects creatures restrained by the spell. So it is implied that there has been one failed save.
If it successfully saves against this spell three times, the spell ends. If it fails its saves three times, it is turned to stone and subjected to the petrified condition for the duration.
The creature must now make three successful saves to break out of the restraint/spell. The wording is, “If it successfully saves against this spell three times”. It then uses the same wording, “If it fails its saves three times,” with regards to failing saves. This would imply that the initial failure is no longer a concern. This condition wouldn’t even matter if they passed the initial save.
If the first failure counted, then the phrase would have been “If it fails its save twice more”, or something to that effect. The key being “more”; a reference to the earlier failure. Lacking any reference, both implied or directly, would seem to indicate that the creature is starting from zero.
Also keep in mind, that this would be the same mechanism as death saving throws and the Contagion spell; best 3 out of 5.