My third-grade teacher told us how misguided the standard textbooks were to call Australia a continent and Greenland just an island. She showed us, on her Mercator projection map, that anyone could see Greenland was clearly much larger!
Disillusioned I was at age 8. 
But maybe it was a blessing in disguise! 
Here is something that is not an urban myth. The daily newspaper used to include a kids’ page on Wednesday, done entirely by Betty Debnam. It had some facts, some cartoons, and some bad jokes. I think it was national–at least, I’m pretty sure anybody local wouldn’t have made the mistake.
One Wednesday there appeared a map of the United States. I looked at it and it took me awhile to figure out what was wrong. There was no New Mexico! Arizona and Texas were both a bit misshapen to accommodate the absence.
How did she do that? Did she not look at some other map for reference? Did she think…well, I don’t know.
At that time I had a kid who could draw the US, freehand, and did a better job than that. We put the newspaper page up on the refrigerator as a Bad Example. After all, this section was supposed to be educational! (Par for the course for daily journalism, though.)
As far as I know, she never posted a correction.
New Mexico magazine has long had a column called One of our Fifty is Missing, collecting examples of people not believing that New Mexico is part of the US.
Do people in New Mexico refer to Mexico (the country) as 'Old Mexico"?
The El Paso tourism industry as long billed itself as being “at the corner of Texas and Old Mexico”.
New England was called that because of all the people that came from England, moved there and pushed out the locals…
Someone claimed to me that in 1972 when distributing campaign literature for George McGovern, one of the people that they were handing pamphlets to told them that McGovern wasn’t even an American, since he was from South Dakota.
Actually McGovern was born in Kenya. 
I grew up in New Mexico and we used to travel a lot. When traveling in the U.S. I had all kinds of wacky questions from people who should have known better.
‘Do you have a green card/do you need a passport?’ This was from people all over the place but it seemed to happen most back east. The funny thing about this is that I was a blond haired, blue eyed kid who didn’t speak spanish.
‘Can you drink the water?’ The default answer to this was ‘No, we all drink Dos Equis’.
‘Wow, you are really white for a Mexican’. Yes, this was said to me. More than once.
Slee
From my numerous business trips to Albuquerque, I can tell you that they do.
From my living in New Mexico for more than 18 years, I can hardly recall anyone doing so. New Mexicans have no problem distinguishing New Mexico from Mexico. Maybe they thought you were a yokel and felt the need to distinguish it in your presence.
While in Key West at the Hemingway house, the docent asked where we were from. When we said El Paso, she welcomed us to the United States. This was in an actual tour group, and I was too stunned to respond.
Funny, when I tell people in the US that I am from México, they adamantly tell me “you can’t be Mexican”.
I thought there were also issues with the 1996 torch relay, and that the original route omitted New Mexico and had to be amended. I’m looking for corroboration, although the map on this site makes it plausible. I’ll keep looking.
Thank goodness our state was named after the Duke of York, and not the Duke of Canada 
I can tell you for a fact that there is no New Mexico in the US, and I say that as a resident of the great state of New England.
From my experiences in El Paso, this was the correct response.
/lived in Las Cruces for four years
Beat me to it. they’ve been running that column since at least the 80’s, and have never seemed to have a shortage of material.
I seem to recall once receiveing a package from New Mexico, addressed to BrotherCadfael, Yadda Yadda Street, Burlington, Vermont, **Canada **05401.