You are in fact correct that the boundaries of the Voronoi cells on a non-Euclidean manifold need not be geodesics. Consider for instance the manifold which is

You are in fact correct that the boundaries of the Voronoi cells on a non-Euclidean manifold need not be geodesics. Consider for instance the manifold which is a cone with a circular base, and let the sample points be the apex of the cone and the center of the base. The boundary of the two cells thus produced will be a circle parallel to the base, which is not a geodesic on the cone.