How are you defining temperature? I assume it's not average kinetic energy of the particles. Is it that definition I learned once upon a time where T = d entropy /d energy? Is this a useful definition of temperature if it leads to this scenario?
A system at finite negative temperature is actually considered "hotter" than a normal system at any positive finite temperature; if you put them in thermal contact, heat will flow in the direction that increases entropy, which you get by taking energy out of the negative-temperature inverted system and adding it into the ordinary positive-temperature system. This increases the entropy of both systems.
The definition where temperature is the "average kinetic energy of the particles" is a special case, and it only really works when that energy is evenly distributed over all degrees of freedom. For example, you wouldn't consider an icy comet to be at a high temperature just because it's moving quickly, even though its particles have a great deal of kinetic energy on average!
The first thing to understand is microstates, which is just the number of ways a system can have a certain energy. Eg in a two-state system with ten particles and energies +/-(E/2), there's one microstate where the energy is -5E (all negative), ten states with -4E (one elevated), etc. Then entropy is just the log of the # of microstates, which is much easier to deal with, since microstates tend to behave exponentially. Eg entropy(E=-10) is log(1)=0, entropy(E=-9) is log(10), etc.
Then temperature like you said is d(entropy) / d(energy). Two systems with different temps brought into contact will exchange energy until the temps are equal, since this configuration maximizes entropy.
The two-state system can have negative temperatures since entropy starts decreasing with energy once more than half of them are in the higher-energy state. This can't happen in more familiar scenarios (eg ideal gas, blackbody, etc) since usually entropy always goes up with energy.