Casinoland
Que-no (?)
Trinity (although the religeous people will probably get upset)
RedorGreen (?) 
The name should be
IknewIshouldvetakenthatleftturnat
The Forbidden Zone.
I like Encanto! or … Enchanto!
I prefer Newcular Mexico myself.
Mexicousa!
Cowboyland.
Alientopia.
You know how they say that in advertising, the only word more powerful than “new” is “free?” How 'bout:
Free Mexico
It already has one. It’s part of Aztlán;
AntiTexas.
I think that this thread is way too limited in scope - why don’t we eliminate all state names that refer to foreign cities, nobility and monarchs… Then move on to adjust city names like Baltimore - we are America - no nobies here.
Even California seems off to me - I nominate “Nixonia”.
How about Reaganland?
“Used Mexico”
or
“Previously Owned Mexico”
.
Square-Plus. (Nickname: “The Stair Step State”.)
Seriously, what up with that? Didn’t want to give up that extra bit of whole lot of nothing? Couldn’t bear to have the entire state sit north of El Paso? Teenage rebellion against the rectangle mentality? And even still, why the jaggies? Just shape your bottom border like reverse Arizona and be done with it. (Arizona, we’ll discuss your western boundary issues later.)
So, yeah, Square-Plus it is. Also, they should fight to keep the hyphen in the postal abbreviation…if AZ can choose to ignore Daylight Saving Time, S-P can do the same for postal conventions, no?
In this day of non-absolutes . . .
Newish Mexico.
(Funny, you don’t look . . . )
New and Improved Mexico.
New Mexico becomes TexMex.
California becomes (is) North Baja or Mexifornia, take your pick.
But TexMex doesn’t have green chile.
This is brilliant.