Happily since this is a practical question, one does not need to solve Theseus' Paradox to provide an answer. The intent behind the rule is to provide distinctive work, i.e., no reader will think "I have read this before." To determine whether a new work is too similar to a previous work, one should consider whether a reader would think the work had been read before from fallible memory of perhaps a year earlier.
Trying to play lawyer with the definitions of "same work" and "previously published" will not endear one to editors. In fact, being upfront about the relationship — while also demonstrating that one is familiar with the submission guidelines and does not expect special treatment — may slightly increase the chance of publication.
On the practical matter, if I were an editor, I would consider such minor changes to be revisions and quickly reject the submission (if I knew the previous work had been published). The two works are sufficiently similar that a reader who had read one a year after the other could easily think them the same. Both use substantially the same form, both have the same tone, both use the same imagery, and both cover the same subject (in this case made more obvious by the reference to "The Road Not Taken", which would make those aspects more memorable).
Note that the rule about previously published is subject to the editor's discretion. For example, a mediocre work published in a poetry magazine with very low standards (e.g., some college poetry magazines) that was substantially refined such that it would be eagerly accepted for publication if it had not be previously published would typically be considered as if it had not been previously published. A typical reader would not think them the same work from memory (even if all the above mentioned traits were the same); in fact, a reader presented with both would likely think the earlier work a weak imitation of the latter. Furthermore, the obscurity of the earlier publication would make the editor feel that readers would be even more likely to appreciate the work as new.
If one has some juvenilia that was "published" in a high school poetry magazine, one might be able to refine such works into what would be accepted as new by a poetry magazine with high standards. Similarly, if one took a well-written and previously published Shakespearean sonnet and revised it into a Petrarchan sonnet of the same or better quality, the modest difference in form and presumed changes in images and tone (a Shakespearean sonnet traditionally has a two line "conclusion", while a Petrarchan sonnet has a turn after the first eight lines) might be sufficient to be considered new. In that case, an editor might appreciate being exposed to both version (and might even desire to republish the earlier version to highlight the contrast).
In general, it is not a good idea to submit a revision of work that has been previously published when the publisher requires that submissions not be previously published.