Pull a Prince and change the name to that sun symbol from their flag.
“New Mexico” name change ideas: Original inhabitants and settlers which consists of Indian tribes, Mexicans, and Europeans explained in an acronym.
1# choice
◇ Zampenca ◇
Z - Zuni
A - Apache
M - Mexico
P - Pueblo
E - European
N - Navajo
C - Cherokee
A - Anasazi
What do you think?
2# choice
Zeparava
Z - Zuni
E - European
P - Pueblo
A - Apache
R - CheRokee
A - Anasazi
V - Navajo
A - Athabasken
3# choice
Zempanca
Z - Zuni
E - European
M - Mexico
P - Pueblo
A - Anasazi
N - Navajo
C - Cherokee
A - Apache
Let’s just call it Mexico, then the Donald’s wall will get built around it, cause Colorado always wanted to be a southern border state.
Other ideas
Zanecpa - acronym
Ziapada (Zia sun symbol)
Zacomha (acoma pueblo)
Zibado - random
Zavoma
Zavopeche
“Z” choice to be first state to start with that letter.
Land of No Customer Service
Green Chileania
Zombie Threadlandia
Grrmerica (pronounced Gurm-erica), since it’s where George R. R. Martin (GRRM) lives.
I support this. Not only would we have a state with a name that starts with “Z”, but it would be the shortest state name. That is, until Southern California splits pff and gets named “Que” (although some will claim that the name for Southern California is actually 5 letters because you have to include the question marks).
North Chihuahua
or
Since a major New Mexican city was named after a game show, we could rename the state itself: Shop 'til You Drop!
Which, unfortunately, is incompatible with Windows 7 and beyond.
Ya know, zombie thread or not, one thing to bear in mind is that Te(j/x)as, Nuevo Méjico (then including most of Arizona and bits of Colorado) and Alta California (then including Nevada and much of Utah) already had those names before we took them over. So blame President Polk for not paying attention. And I’d want to deal with St. Petersburg and Naples FL, Rome/Syracuse NY, Venice CA, too, and while we’re at it settle on only one Springfield.
“New Sexico”
“Lee Van Cleef”
…
…
Well, why not?
…
…
I’ll get me hat…
I was thinking of West Texas, or West Oklahoma (or Westahoma?), but I could be talked into South Colorado.
I guess I’m not very original. 
Southwest West Virginia.
East Southwest Norte?
From what I saw in Artesia, NM: New METHico
Macho Grande
(I’ll never be over Macho Grande)
Santa Fe, then some bills and letters can be sent to SF, SF
I think any name change should reflect the reason for the change. So I nominate Ipotusi.
As in: It’s part of the United States, idiots.