Assuming that Neil deGrasse Tyson is referring to the cosmic event horizon, he's right. But that doesn't really mean that galaxies "fall out of sight". He's right that they will disappear, but not because they leave the horizon.
Nearby galaxies don't disappear
First of all, there's a small thing to note that I'm sure he just left out to simplify matter a bit:
The Universe expands and drags galaxies along, but for galaxies that are sufficiently close, their mutual gravitational attraction keeps them "locked". Hence, we will always be able to see the galaxies in our Local Group. In the case of Andromeda, we will even end up merging, and I suppose that after a sufficiently long time, we'll merge with the other galaxies in our group, simply because we will keep orbiting around each other, so at some point we'll come so close so as to merge.
Galaxies don't leave the observable Universe…
Second, and more importantly, galaxies do not leave our observable Universe. The observable Universe consists of the region of the Universe from which light has had the time to reach us since Big Bang, and the "boundary" between the observable and the un-observable Universe is called the particle horizon. As time goes, the light from an ever-increasing number of galaxies will have had the time to reach us. This number will never decrease. Once inside our observable Universe, a galaxy will stay inside.
…but fewer and fewer galaxies will be able to send a light signal to us…
However, the distance at which galaxies may emit a light signal today, that we may receive some day in the future, only asymptotically increases to a finite value (of some 17 billion lightyears; see e.g. Davis & Lineweaver 2004), while the galaxies themselve continue to increase their distance. I suppose this is what Neil deGrasse Tyson refers to: Even though the galaxies we see don't vanish from sight, we will never see what's going on in them today.
…and in practice, even the ones we see now will disappear…
Moreover, even the galaxies that we do see will become increasingly redshifted until eventually all light from them will be in the radio regime. Furthermore, photons will arrive at a smaller and smaller rate, until for all practical purposes, they will be invisible to us.
…especially if $w>-1$
The above considerations hold true if the Universe expands, and accelerates, as we think it does. However, there is a possibility that the acceleration itself will increase in magnitude. If the equation of state $w$ of the dark energy thought to be responsible for the acceleration is smaller than $-1$, the distance to the point where the Universe expands faster than the speed of light may decrease indefinitely, such that galaxies will indeed leave the horizon. Eventually, even gravitationally bound galaxies will be separated, stars will be torn out of the galaxies, planets will be pulled from the suns and finally disrupted, culminating in a Big Rip.