Bush won the Gore/McCain NY and NJ counties in 2004.
Might it be population loss in those counties that changed them over the last decade?
I am not too familiar with NY politics despite having lived there for a short while.
That's definitely not the case for Richmond County, NY, which alone has a growing population larger than many small cities. It's voted Republican in every election since 1944 except 1964, 1996, and 2000.
Why 2000 though? I know Gore did extremely well in NY but still...
Well the "moderate" impression of the Clinton-Gore administration that delivered Richmond County to the Dems in 96 might have carried it again for Gore in 2000. I know many people felt that the economy was doing well and wanted to stay the course with Gore. When the "war on terror" was a big issue four years later, Bush got quite a bounce throughout the NYC area.
As for Montgomery County, that's a sparsely populated upstate county that voted for Dukakis in 1988 but then apparently trended Republican in the 2000s.
Ironically Hillary Clinton lost both of the NY Gore-McCain counties in her 2000 U.S. Senate race.
https://uselectionatlas.org/FORUM/index.php?topic=112446.0There's been a decent trend for NY and NJ Whites from D to R from 2000 to 2008.
It's more the case of Bush horribly under performing in both NJ and NY in 2000.