Your hypothesis that
if you have something like:
$$\frac{1}{kT}=\left(\frac{\partial S}{\partial E} \right)_{N,V}$$
And they've created a situation where entropy decreases with increasing energy.
is exactly right. The concept of negative absolute temperature, while initially counterintuitive, is well known. You can find a few other examples on Wikipedia.
In your question you say that temperature is "the average kinetic energy of ... particles". Strictly speaking, this is only true for an ideal gas, although it's often a good approximation in other systems, as long as the temperature isn't too low. It's slightly more accurate to say that temperature is equal to the average energy per degree of freedom in the system, but that's an approximation too - energy per degree of freedom would be $E/S$, whereas $T$ is actually proportional to $\partial E/\partial S$, as you say. It's much better to think of $\partial E/\partial S$ as the definition of temperature, and the "energy per degree of freedom" thing as an approximation that's useful in high-temperature situations, where the number of degrees of freedom doesn't depend very much on the energy.
As Christoph pointed out in a comment, the significance of the new result is that they have achieved negative temperature using motional degrees of freedom. You can read the full details in this arXiv pre-print of the original paper, which was published in Science.