Fréchet means are a popular type of average for non-Euclidean datasets, defined as those points which minimise the average squared distance to a set of data points. We consider the behaviour of sample Fréchet means on normed spaces whose unit ball is a polytope; this setting is rarely covered by existing literature on Fréchet means, which focuses on smooth spaces or spaces with bounded curvature. We study the geometry of the set of Fréchet means over polytope normed spaces, with a focus on dimension and probabilistic conditions for uniqueness. In particular, we provide a geometric characterisation of the threshold sample size at which Fréchet means have a positive probability of being unique, and we prove that this threshold is at most one more than the dimension of our space. We are able to use this geometric characterisation to compute the unique Fréchet mean sample threshold in the case of the $\ell_\infty$ and $\ell_1$ norms.