Do you remember the source? I'm looking at two that point to October 1985. NOA's press site says "Originally released on NES, October 18, 1985" for SMB on Virtual Console, and all the SMB-related trophies in Super Smash Bros. Melee say "10/1985," for example: http://themushroomkingdom.net/mariopedia/trophy/goomba.jpg
Hmm... when was the New York, regional release of the NES? The one that predates the nationwide release? A cursory internet search seems to say that the NES was released in New York on October 18th, 1985 - but the list of initial release games doesn't contain SMB.
I seem to recall reading, in multiple places, about the limited initial release - and that includes SMB not being in the initial release. I, however, was assuming the October '85 date was the national and it was an earlier date for a regional, but that's clearly not correct.
I could see NOA being wrong about this. Perhaps we should contact them.