Wow. That’s insane - I didn’t know there was anywhere you could lose your citizenship because “you never call, you never write!” Sounds like what you want is to become a US citizen ASAP. It’s not like there aren’t benefits - don’t you want to vote and all, since you obviously live here and don’t plan on leaving permanently?
I can indeed confirm that right to work in the US is totally different to the right to re-enter the US (leaving of course is easy, its getting back in that can be a problem). I have a completely separate set of paperwork for the latter that has to be applied for with it own set of arcane paper work (the bit I need to re-enter the US is awesomely called “advanced parole”, which sounds like I am an ex-con).
Additionally staying outside the US too long (6 months if I remember rightly) will invalidate your green card.
Basically talk to a lawyer is you are worried. There is a sh*t-ton of arcane rules and the internet is not the best place to get an accurate description of all of them 
Maybe Ukraine is somehow trying to see to it that Russians who were in Ukraine at the dissolution of the USSR did not retain Ukrainian citizenship after relocating back to Russia.
Not to mention Jews. That was the issue with one semi-client; she had left as a refugee with her family when she was a small child, and had never gotten around to naturalizing in the US (she was by then in her 20s). Her passport had expired, and when I went with her to the Ukrainian Consulate, as soon as they saw her expired passport with “nationality - Jewish” and “departed for permanent residence abroad” stamped in it, they basically told her she was SOL as far as renewing her passport was concerned.
The reasons given were all over the map the numerous times we asked for an explanation, and when I asked where I might find a printed copy of the citizenship laws of Ukraine so we could come up with a plan of action that would allow her to travel internationally, the response was “it’s on the Internet in Ukrainian, so your client can read it.” (The client, as is the case with almost half the residents of Ukraine, is a Russophone and can barly fumble her way through grade-school Ukrainian, certainly not enough to decipher legislation.)
AAAAARGH. Fourthing, or whatever, the recommendation to talk to a qualified immigration lawyer, preferably one with practical experience in dealing with the special challenges of post-Soviet bureaucracy.
Interesting. This is not exactly the same, but Hong Kong has something similar with its “right of abode” issue. The absolute, undeniable right to live in the territory, as well as the right to vote and a few other rights that, in other places in the world, are normally considered the privileges of being a citizen, are not conferred through the person’s nationality, but with a separate legal status called the right of abode instead. For example, regardless of nationality, only people who have the right of abode have the right to vote in local elections. However, the right of abode of a non-Chinese national will automatically expire after an absence of more than 36 months. Similar to the Ukrainian situation, yes, this is also a new rule intended to revoke the rights of foreigners from “the old day” who have returned to the mother country.
I know that in the aftermath of the recent war in Lebanon, Canada vowed to strengthen its citizenship rules to prevent “citizenship of convenience”, that is, people living in their home countries for years but who also have a Canadian passport so they can get “repatriated” fast to Canada in case something happens in their homeland. But I don’t know what the current rules are; I don’t know if they could get their citizenship revoked or if the government has just made it harder to obtain Canadian citizenship.
Also, Ombak, there are several non-profit organizations that can help you with this, if you qualify. Here’s a link to the Appleseed Network. Catholic Charities and Lutheran Family Services in your area may also provide sliding scale or pro bono immigration services.
Thanks for all the info guys. It’s much appreciated!
I can’t help you with the expense, but depending on your parents’ age, they may not be required to pass the English exam. See p. 26 of the attached USCIS naturalization guide.
Awesome! Thanks Eva!
As usual, the government here was all talk and no action. No surprise.
The idea was to stop people from becoming naturalized Canadians, as many Lebanese refugees did in the civil war over the 1970’s and 80’s; then heading back to Lebanon 10 or 20 years ago - never to be heard from again until they dug out their pasports and asked to be rescued, at great expense to Canada, from the recent invasion.
IIRC the discussion at the time mentioned something about how losing naturalization was possible in several countries when your time outside exceeded your total time in the country.