I assume fast travel does not warp him as well?

If it's a pathfinding issue maybe try teleporting him to a new position?