Solution:

First consider the minimum number $m$ in the table. If it appears in some cell $A$, two neighboring cells $B, C$ must also contain $m$ because there is no other way for $m$ to be the arithmetic mean of two numbers in the table. Since $B$ cannot neighbor $C$, it must have another neighbor $D$ in addition to $A$ that contains $m$.

So the minimum number in the table appears at least four times. Likewise, the maximum number appears at least four times. We can now find 8 cells that contain at most 2 distinct numbers. The remaining 56 cells of course contain at most 56 distinct numbers. So there are at most 58 distinct numbers in the table. The diagram below shows that this bound can be achieved.