When I lived in Alaska, in the mid-80’s, there was a well-publicized incident where a well-known East Coast airline (Delta, I think) refused to consider a local girl for training as a flight assistant, as they only hired Americans. I seem to remember this happening once every couple of years, always geting front page publication in the newspapers.
Since this thread has wandered off course, I will add a good friend of mine who claims to doubt the existence of North Dakota. He asks me if I have ever met anyone from there and I can’t say I have. Of course, I have never met a New Mexican either. Or an Idahoan, for that matter. My friend, incidentally, is from Providence and you cannot even find his state on a map. It is the smallest state with the longest name (Rhode Island and Providence Plantation).
When you start electing good ol’ Democrats and Republicans and not these sissyboy Progressives and Independents, we’ll let you come back 
I have two students who sat at the same table in one of my classes find out two weeks before finals that their families live in the same town in North Dakota, Buckshot Junction
I worked with a guy who lived in N. Dakota and got his PhD there, his wife was from there. Other than that I don’t think I met anyone from there.
Wait wait wait let me get this straight. If McGovern was actually born in Kenya then that must mean that Obama was actually born in South Dakota.
I knew it! I knew he was a damn foriegner.
I had to explain to a shipping clerk at a company I worked for that New Mexico is an official part of the United States of America; she thought she needed special paper work to ship an order to New Mexico, it being out of America and all.
It happens enough that there are jokes based on the mistake and they don’t need explaining to anyone who lives in NM.
Do we know more about the Atlanta thing about New Mexico? Was it simply a minimum-wage call center employee that didn’t know geography too well? The type who ask me what it’s like to leave Hawaii and come back to the States?
Or did management or Olympic representative get on the phone and insist that New Mexico is part of Mexico?
Well of course you’d need a passport to go from New Mexico to Atlanta. Atlanta is in Georgia.
What, Nevada?
As for the original question in the OP, that’s the way I remember the story being reported in the local media. Someone with Lexis access could search the Albuquerque Journal for that time period and should probably find the story.
A search of the local archives for the Journal shows that Pete Domenici "took it upon himself to refresh his colleagues’ knowledge about the Land of Enchantment.
“New Mexico, yes, that large span of land between the oil wells of Texas and the saguaros of Arizona, is in the United States,” Domenici, R-N.M., said on the Senate floor." That article was March 4, 1996.
That’s the best I can do without better search tools.
(Grew up in Albuquerque. You can tell when I slip up and pronounce the Al in Albany the way you pronounce Albuquerque.)
I’m from Tennessee, but when I was a child in the Forties, it was fairly common to refer to Mexico as “Old Mexico.” Of course, it’s possible that I picked that up from an overdose of Western movies.