The average velocity of a SHO is 4 times the maximum velocity? I am looking at simple harmonic oscillators. The maximum potential energy is equal to the maximum kinetic energy:
$k {x_{max}}^2 = m {v_{max}}^2 \rightarrow x_{max}=v_{max}\sqrt{\frac{m}{k}} = \frac{v_{max}}{\omega}$
Also, the time to find the average speed, calculate the total distance traveled over one oscillation by the total time it takes.
$v_{ave} = \frac{4 {x_{max}}}{\tau} = 4 {x_{max}} \omega$
Now if I plug in the first result into the second result I get:
$v_{ave}  = 4 v_{max}$
But surely this is not right.  The average speed is equal to 4 times the maximum?  How can this be?
 A: You made a simple mistake converting time period to angular frequency: $\omega = \frac{2\pi}{T}$, so $\frac{1}{T} = \frac{W}{2\pi}$.
I will not work it through for you, but you should get the answers you are looking for.

If you are interested in working out max velocity and average velocity in general, i.e. not just a mass on a spring, then you could use the general SHO wave equation:
$$y = A\cos(wt).$$
Where  $y$ is the displacement and $A$ is the amplitude (your $x_\text{max}$).
We can differentiate to find the velocity,
$$\frac{dy}{dt} = -Aw\sin(wt).$$
From which we can calculate the average velocity and maximum velocity.
The maximum velocity is easiest as we know the largest value of $\sin(wt)$ is one, so
$$v_\text{max} = \text{max } \left|\frac{dy}{dt}\right| = Aw.$$
Which is what you got: $v_\text{max} = x_\text{max}w$.
The average velocity is a little harder. The average value of a function $g(x)$ in the interval $[a,b]$ is defined as
$$\frac{1}{b-a}\int_a^bg(x) \, dx.$$
So we could take the interval to be one time period (because any more and it just repeats itself!), but the problem with this is that we will just get zero for the average velocity ($\frac{dy}{dt}$). This is because the average value of $\sin$ from $0$ to $2\pi$ is zero and $w$ just stretches this graph.
The mistake we have made is that we actually want to find the average value of the speed, $\left|\frac{dy}{dt}\right|$, given by the integral
$$\frac{1}{T}\int_0^T\left|\frac{dy}{dt}\right|\, dt = \frac{Aw}{T}\int_0^T|\sin(wt)|\, dt$$
There are two ways I can see of evaluating this, either write $|\sin (wt)|$ as $\sqrt{\sin^2(wt)}$ and use a double-angle substitution, or we can use the symmetry of the sine function, seen below.

From this symmetry, we can see that
$$\int_0^{2\pi}|\sin x| \, dx = 2\int_0^{\pi}\sin x \, dx$$.
Or in our case,
\begin{align}
\frac{Aw}{T}\int_0^T|\sin(wt)|\, dt &= \frac{2Aw}{T}\int_0^{T/2}
\sin(wt)\, dt \\
&= \left. -\frac{2A}{T}\cos(wt)\right|_0^{T/2} \\
&= -\frac{2A}{T}\left[\cos\left(\frac{wT}{2}\right) - \cos(0)\right] \\
&= -\frac{2A}{T}\left[\cos(\pi) - \cos(0)\right] \\
&= -\frac{2A}{T}\left[(-1) - 1\right] \\
&= \frac{4A}{T} = v_\text{ave}
\end{align}
which is of course what you got with the simpler $\text{speed} = \frac{\text{distance}}{\text{time}}$ approach: $v_\text{ave} = \frac{4x_\text{max}}{T}$.
So although your inkling that the average speed shouldn't be greater than the max speed was correct and solved by the simple calculation error I pointed out at the start, I hope you can learn something extra from this answer in the form of an alternative, more mathematical approach, that you could have taken.
I will conclude with the final results.
\begin{align}
v_\text{max} = Aw && v_\text{ave} = \frac{4A}{T} = \frac{2Aw}{\pi}
\end{align}
