Sucktana
Mogoanasaziville
George.
“Not The Other Mexico”
or
I’ll second “Sucktana”
Let’s call it Nuevo Mexico. That will clear up any confusion.
Same Ole Mexico.
Alba Koikee.
Gadsden’s Folly.
Greater Roswell.
Truth.
Consequences.
"Think here now–THINK! Ok, ok, ok… we got a state here with some branding issues… a stale, old name even though it’s called “New”… we gotta spice this thing up!
Think–‘what’s newer than “New”?’ Take it to another level, ya know? Hmmm… we gotta get it across to the consumers that something Bright 'n Shiny is happening here. Something big. Something WOW…! Something that says: "New Mexico is better than ever before and yer gonna love it here!
OK. Who’s got something for me here…? C’mon gang… let’s run with it, OK?"
“Uh… how 'bout New and Improved Mexico?”
[Ed Wood]
“Perfect!”
[/Ed Wood]
Up the confusion level. Call it Aztlan. 
Extreme West Florida?
Chihuahua del Norte?
Nouveau Québec?
Pepsi Presents Welcome to the state of Raymond James University of Phoenix Qwest by Microsoft.
France!
West West Texas
Chupacabra.
I’m a native New Mexican, and I thought most of the stories about people nowadays thinking New Mexico was part of Mexico were apocryphal.
At least it’s not Constantinople.
Aliena
We could get sponsorship:
New Mexicoca-cola.
Del Norte.
Baja Colorado
Really West Virginia
Chile. That should clear up any confusion.
Om.
Kokopelli Or maybe not.
Sopaipilla Hey, they taste great! And spelling-difficulty-wise, no worse than lots of other states.
"I can’t believe its not Mexico"™
Un-Mexico