I had to read it several times to make sure I wasn't misunderstanding somewhere, but the molecules don't appear to actually have a temperature below absolute zero. What they're talking about is the energy distribution - instead of many molecules being at a low energy state and only a few being at a high energy state, they've managed to invert this so that most of the molecules are at a high energy state and only a few are at a low one. That results in what they are apparently calling a negative absolute temperature, but what it actually means is that the gas apparently has properties which would be associated with a negative absolute temperature, not that it is at a temperature lower than absolute zero. The gas molecules are all at a few billionths of a degree higher than absolute zero, but that's what makes this work.
Basically, these gas molecules have an upward limit on the amount of kinetic energy they can possibly have, due to being so close to absolute zero. By insulating them within an ultra-high vacuum and using an optical lattice to limit their ability to interact with each other, they apparently can't lose what kinetic energy they still have. As a result, they'll tend to cluster at areas of high potential energy, and achieve an inverted distribution (which is the same as having a negative absolute temperature, even though they don't actually have one). So they can absorb energy from both things that are hotter than they are (as normal) and things which are colder than they are too. That's where the thermodynamic efficiency of over 100% comes from, since normal thermodynamic engines can only absorb energy from a hotter medium, and they lose energy to a cooler one. A thermodynamic engine which can absorb energy from a cooler medium would negate this and have an efficiency higher than 100%, because instead of one-way heat diffusion, it isn't diffusing heat at all.
If you leave a hot cup of coffee out, it tends to cool off as the heat diffuses into the surrounding molecules. If you leave it in the sun, it will absorb heat from the sun but still lose heat to the surrounding molecules. This is like finding a cup of coffee which absorbs heat from the surrounding molecules as well as from the sun and thus is hotter than you would expect. Its efficiency would be higher than 100%, but only because it's able to absorb heat from the surrounding molecules.
It's weird, but it seems to hold together.