The variance is calculated based on the average variance of all point pairs within each interval of the cell size. The variogram is then fit to the variance points using the Levenberg-Marquardt method (Press et al., 1986) of nonlinear least-squares approximation. A minimum of three points (a variance value at three distances) is required for the fit.
The following message indicates that there were not sufficient points to calculate a variance at the minimum of three distances: Unable to estimate semivariogram.
Reference: Press, W.H., et al. Numerical Recipes in C: The Art of Scientific Computing. New York: Cambridge University Press, 1988.
By increasing the cell size, you will increase the number of sample points per cell size interval, thereby providing enough data points to estimate the semivariogram. Once the semivariogram is estimated, a smaller cell size can be used in creating the actual output raster.