Gabriel/Niko,
I agree with both of you. The words of the hymn should NOT be altered. No doubt, this "change" came about because of the disdain towards the king and the monarchy in general.
Years ago (and specifically, since 1974, I would assume), the Church of Greece, in their annual Hemerologion (now called the "Dypticha") had a short section titled, "Τελετουργικαί επιπτώσεις από της καταργήσεως της Βασιλείας" (loosely, "Teleturgical effects since the abolition of the Monarchy"). I don't believe this is being published any more in their annual Dypticha because... well, it's been quite a while since the monarchy was abolished and they must feel it makes no sense to do so any more. This section outlines exactly what can or can not be changed/altered/left out from the various hymns and prayers that reference kings or monarchs. I won't translate the entire article, but I'll give you the gist of it. After a short explanation about the matter, there are three subdivisions which I can outline here for you:
1. Deleted and omitted hereinafter:
a) Τhe "Polychronion";
b) Τhe commemorations of the kings during the Great entrance, in the "Eirinika" and in the "Ekteni";
c) The "Lord save the kings" ("Κύριε σώσον τους βασιλείς") during the hierarchical Liturgies, instead doing a triple-repetition of "Lord save the faithful" ("Κύριε σώσον τους ευσεβείς").
There is a notation here that the rubrics and prayers of the formal Doxologies of January 1, March 25 and October 28 are offered in their respective places in the Hemerologion book.
2. Preserved unchanged, as is:
a) The prayers of the Divine Liturgy, wherever the monarchs are commemorated (e.g. After the "Se ymnoumen": "...We also offer to You this spiritual worship for the whole world; for the holy, Catholic, and Apostolic Church; for those living in purity and holiness; for the most faithful and Christ-friendly kings, all of the palace and of their camp. Give unto them, Lord, a peaceful kingdom, so that we, in their peacefulness, may live peaceful and serene lives in all piety and holiness." (Note: the phrase about the "Christ-friendly kings", the palace and the camp has been replaced in most English Liturgical texts with something about "those in public service".)
b) The Apolytikia, Kontakia, Doxastika and other hymns which deal with kings (e.g. the Indictus, "... protect in peace the kings and your city..."; the Elevation of the Holy Cross, "Lifted up on the Cross by Your free will... Gladden our faithful kings by Your power..."; and similar hymns).
c) The petitions for the deceased Kings, Patriarchs, Hierarchs, etc.
3. Acceptable (but not imposed) omission of:
a) In the Dismissal prayer, the phrase "...our kings..." (without substituting with another phrase, such as "to our rulers").
b) In the Small and Great Blessing of the Waters, the phrase, "...and protect, O Lord, Your servants, our faithful kings... (up to) make them lenient in every way towards the nation of the Christians who serves You." [Small Blessing of the Waters] or up to "...every enemy and adversary" [Great Blessing of the Waters]. (Sometimes "kings" is translated as "rulers" in English, but in Greek, "βασιλείς" should never be substituted with something like "άρχοντες".)
That's basically the meat of the whole thing. The article then makes a specific mention about the hymn "Σώσον Κύριε τον Λαόν Σου", and notes that the phrase "νίκας τοις βασιλεύσι κατά βαρβάρων δωρούμενος" should NEVER be substituted with "νίκας τοις ευσεβέσι κατ' εναντίον..." because this hymn and the other two that accompany it before the Exapsalmos ("Ο υψωθείς... εύφρανον εν τη δυνάμη σου τους πιστούς βασιλείς ημών..." and "Προστασία φοβερά και ακαταίσχυντε... σώζε ους εκέλευσας βασιλεύειν...") are historically established as prayers and that the words "vasileis" and "vasilevein" can also mean, in general, "rulers" and "those who rule". The article references some passages from Luke, the First Epistle of Paul to Timothy and the First Epistle of Peter to further make its case. On the whole, it's really a good article and there is no question as to what needs to be followed.
I hope this has been helpful. If anyone has already scanned this section from a prior-year Hemerologion book of the Church of Greece, please upload it. If not, I'll try to do it sometime in the next week or so. The article is entirely in Greek, but I have given you the main points, above.
Apostolos