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.
It's not true for Monmouth County, NJ, either, which is a growing suburb/exurb of NYC.
Montgomery County, NY is fairly small (just under 50,000) and losing a bit of population. It's a largely rural county between Albany and Utica.