That’s not a good reason either. The word wasn’t being used in its modern sense, it simply meant a colony.
Here’s OED:
And people say I’m good for nothing:p
The fact that other states might have a cost imposed on something they do by the fact that Rhode Island changes its name does not mean that the Commerce Clause is implicated. Even under the loosey-goosey standards of reviewing Commerce Clause actions by Congress, that’s not enough. After all, there are numerous things a state can do (or a city, for that matter!) that would have the same effect. Are you seriously suggesting that Chicago, for example, needs an Act of Congress if it wants to change its name to Windy Freakin’ City?
Secondly, even if the Commerce Clause could somehow be implicated, that only means that Congress can regulate it, not that it must regulate it, or that, in the absence of such regulation, nothing can be done about it. Suggestion: learn Commerce Clause jurisprudence before using it in an argument. 
The Enabling Act told the territories what they could do. It can only be argued that, had the Territory of Washington gone through their constitutional convention and then applied for admittance as the State of Snohomish, they might have run into trouble for having failed to follow the enabling act. But that doesn’t mean Congress couldn’t have then admitted them under the name State of Snohomish.
As for the statement of one Debbie Howlett, the day you can show me that Debbie Howlett has her degree in the law of such matters, I’ll consider it. Otherwise, it’s just another example of why you cannot listen to USA Today for anything important in the way of factual information. 
New Zealand is referred to only in the definition clause:
Since New Zealand is no longer a colony, I don’t think the specific reference here could help in its admission to the Commonwealth of Australia (if the good people of NZ ever went insane and decided to join). Instead, it would be admitted as a “such … territor[y] as may be admitted into or established by the Commonwealth as States”.
Similar, since the Northern Territory of Australia is no longer “the northern territory of South Australia”, and since South Australia no longer includes it, if the NT ever became a state it would be admitted under the more general clause.
If, for example, New South Wales decided to change its name to something more euphonious like Reesotopia, I think it would help if the Commonwealth Parliament passed an enabling act, saying that all references to “New South Wales” in legislation, regulations and agreements should now be read as referring to “Reesotopia”; but I’m not sure that would be absolutely necessary.
OK, how pedantic do you want to be? Read the enabling act of 1889. Section 5: “SEC. 5. That the convention which shall assemble at Bismarck shall form a constitution and State government for a State to be known as North Dakota”
That was the text that was approved by Congress and thus that is the name of the state.
Without an Act of Congress this can’t be changed. North Dakota may be calling themselves “Bananaland” but the federal government won’t until this Act is amended.
Short answer to the OP: Like I said before, it would take an Act of Congress.
*Debbie Howlett is a reporter for a national newspaper with a editor and fact checker on staff
Another source:
“To change names, officials would have to alter the state constitution and the federal Enabling Act, which split the Dakota Territory into the states of North Dakota and South Dakota in 1889.”
–Associated Press, June 26, 2001, Dale Wetzel
And the third source:
“”‘Dakota’ is a beautiful word," said State Sen. Tim Mathern (D-Fargo), who first proposed the name change in 1989, the state’s centennial. “It reflects our heritage as a clean, wholesome, friendly land of peace. We ought to lead with the noun, not the adjective.” (Judging from how long Mathern has been working on this issue, the noun that comes to mind is “futility.”)
Mathern, who called me from his car phone and was sure to tell me that he was on Dakota Avenue in Fargo, said that it will take “people of courage and vision” to pass the name-change initiative and see it through Congress."
–Newsweek, July 23, 2001.
<sigh>
What they had to do in 1889 (“form a constitution and State government for a State to be known as North Dakota”) is not what they have to do now. It doesn’t mean that the State of South Dakota has to be South Dakota forever, or even that the State known as South Dakota can’t change its name. It simply means, as I stated, that they had to call themselves South Dakota at the time.
As for your other citations, the fact that some people believe that an Act of Congress is necessary, does not make it necessary. People are wrong about these things from time to time; further, they can actually reasonably disagree about them at times.
If what you have is the best authority you can muster, I’m afraid it isn’t very authoritative.
<louder sigh–closer to a groan.>
Now you’re just being silly. I provide cites from three different, respected sources (USA Today, Newsweek and the AP) on a site that often just relies on Wikipedia. One of the cites even quotes the North Dakota state Senator who has looked into this and who would probably have to be part of the process (at least at the state level).
Please make an actual attempt to discredit all of my sources or find me someone of authority to argue your position. Can you? 