New Mexico, considering it was taken from Old Mexico by force by non-Mexicans.
The name existed long before the territorial expansion of the US against Mexico, and in fact long before the modern nation-state of Mexico existed. The phrase "Nuevo México" can be found in the chronicles and journals of Spanish explorers as early as the mid-1500s. It's true that the land was ceded to the US in the Treaty of Guadelupe Hidalgo in 1850, but Mexico and New Mexico had long developed with independent histories until New Mexico passed into Mexican hands in 1821. The gringos who applied for admission to the US as a state in 1912 were simply using a name that had been associated with the region for at least four centuries. If you don't like the name New Mexico, then you should blame the
conquistadores who gave it that name, not the gringos who made it a US state.
The name of the country itself is more of a misnomer, since in the Nahuatl language of the Aztec the word Mexico only refers to the central valley (DF and the surrounding states of Mexico and Morelos and a few others), which is the homeland of the Triple Alliance. In fact, in political speeches, Mexican Presidents usually do not refer to the country as Mexico, but rather as "La Patria."