Why does the minimum energy principle work? The principle of minimum energy states that in a thermodynamic system the equilibrium state corresponds to the minimum energy state among a set of states of constant entropy. I believe I understand the mathematical derivation of this, however, my immediate intuition is that this should not be the case.
People sometimes handwave something like "Thermodynamics should agree with mechanics when entropy is constant" or similar. Other arguments imply some sort of "interaction" with the environment, which increases entropy when one reaches a minimum value of energy (I'm not sure where I have read this, I wish I had a source) but I would prefer to steer away from those kinds of arguments. It is clear to me from the mathematical derivation that this principle does not rely on dynamics, mechanics, or other auxiliary systems to be true, only on the fact that the entropy is a concave function of its variables and that its hessian is negative definite at equilibrium. 
My intuition, however, says that if a system has a bunch of states available to it, and all states have the same entropy, then it should not prefer one state over the other and all of them should be equally good "equilibrium states". This is for sure valid when the energy is constant; I know this has to be wrong when the states have different energies, I just don't see how.
Edit for clarity: As an example of the application of the principle of maximum entropy, consider a system composed of two ideal gasses with fixed numbers of particles in different compartments. The total energy and volume of the system are held constant but the entropies and volumes of both gasses are allowed to change subject to constraints, so that $U(S_1, S_2, V_1, V_2)$ has to be a constant, $V_1 + V_2 = V$ has to be a constant but $S_1$ and $S_2$ can freely change. There are many possible states for this system, but the principle of maximum entropy says that the state that corresponds to thermodynamic equilibrium is the state with maximum entropy $S_1 + S_2$. The principle of minimum energy is analogous but the roles of $S$ and $U$ are reversed, and the energy is actually a minimum at thermodynamic equilibrium instead of a maximum. 
 A: Let me start with the first sentence in your question:

The principle of minimum energy states that in a thermodynamic system
  the equilibrium state corresponds to the minimum energy state among a
  set of states of constant entropy.

which is very close to the statement in the introductory part of wikipedia page you cited. However, this is not a consistent way to express the minimum energy principle in thermodynamics. The reason for inconsistency should become clear by looking at formulas.
In the case a thermodynamic state is fixed by the value of entropy, volume, and number of particles, the fundamental function from which the whole thermodynamic behavior can be obtained is the internal energy $U(S,V,N)$. Now, it is clear that once the independent variables are fixed, a unique value for $U$ is possible. There is one thermodynamic state and it is not clear which should be the states "among which energy should be minimum".
Actually, the correct statement of the minimum principle for energy is the following:
in an equilibrium system at fixed entropy, volume and number of particles, and subject to internal constraints controlled by a set of parameters $X_{\alpha}$, the internal energy is a function  $U(S,V,N;\{X_{\alpha}\})$ and the final equilibrium state, obtained after removal of the constraints, corresponds to the minimum of the energy among the all the possible values of the constraint variables  $X_{\alpha}$ (see Callen's textbook on Thermodynamics for a reference).
Starting from the correct statement of the minimum principle, a first observation is that it is more general than just the convexity property of the function $U(S,V,N)$. Indeed, from the minimum principle, one can derive convexity of $U(S,V,N)$. But there are cases where the minimum principle provides results which are not derivable from convexity. For example, if one can determine different functions of energy at fixed $S,N$, as a function of $V$, minimum energy allows to determine for each $V$ the equilibrium state.
What about intuition? Frankly, I think that in the case of the minimum energy principle, is far from being intuitive. The main reason is that the underlying condition of constant entropy is difficult to manage both from the experimental and from the conceptual point of view. However, since from the minimum of energy $U(S,V,N;\{X_{\alpha}\})$ one can 
easily obtain similar minimum principles for the Legendre transforms of energy (Helmholtz free energy, Gibbs free energy), the difficult condition of fixed volume and entropy can be transformed into the conceptually and experimentally easier conditions of minimum  at fixed temperature and volume or  temperature and pressure.

Edit after a few comments and the editing of the question.

Notwithstanding the previous words of caution about the non-intuitive condition of constant entropy, an example with a fluid system could help to get a better understanding. Let me start recasting in a correct way the situation, if it should be analyzed in term of minimum energy principle.
There is a composite system made by two  compartments such that initially the first compartment contains a fluid (the same in both compartments for simplicity) described by the thermodynamic variables $S_1,V_1,N_1$, and the second by $S_2,V_2,N_2$. $V_1,N_1$ and $V_2,N_2$ remain always fixed.  
The energy of this composite system is the sum of the energies of the two subsystems and, being filled with the same fluid (for example both Neon gas), the same function $U$ of entropy, volume and number of particles describes both. By introducing the subscript $tot$ for the extensive quantities describing the composite system we have $S_{tot}=S_1+S_2$, $V_{tot}=V_1+V_2$ and $N_{tot}=N_1+N_2$. For a given partition of the total entropy into a value $S_1$ and $S_2=S_{tot}-S_1$ (this is the constraint on our composite system) we have 
$$
U_{tot}(S_{tot},V_{tot},N_{tot};S_1)=U(S_1,V_1,N_1)+U(S_{tot}-S_1,V_2,N_2).
$$
The minimum energy principle applied to the present case says that if we eliminate the constraint that system $1$ should have entropy $S_1$, but always keeping fixed $S_{tot}$, the final equilibrium state of the composite system will correspond to the value of $S_1$ which minimize  $U_{tot}$. 
That there should be a minimum can be seen by noting that $U(S,V,N)$, at fixed $V$ and $N$ must be an increasing function of $S$ (let's recall that $\left.\frac{\partial{U}}{\partial{S}}\right|_{V,N}=T\gt 0$). So, $U_{tot}$ is the sum of an increasing and a decreasing (convex) function in the interval $0<S_1<S_{Tot}$ and therefore there should have a minimum. 
It is possible to check everything explicitly in the case of a perfect gas in two equal volume containers with the same density. The total energy is
$$
U_{tot} \propto \left(  e^{\frac{2S_1}{3N_1k_B}} + e^{\frac{2(S_{tot}-S_1)}{3N_1k_B}}  \right),
$$
which has a minimum at $S_1=S_{tot}/2$.
In a less formal way, one could say that the reason for the minimum is directly connected to the constraint of keeping fixed the total entropy. Since entropy is proportional to the logarithm of the number of states, a fixed total entropy in our composite system is equivalent to keep fixed the product of the number of states of system $1$ and system $2$. The way the number of states varies with energy provides the mechanism on which the minimum principle is based.

End of the added part

A final remark on microstates. Discussion of the minimum energy principle can be based, as in the previous paragraphs on a completely macroscopic thermodynamic description. Of course, thermodynamic variational principles can be translated into the language of statistical mechanics. However, statistical mechanics  is more naturally expressed in the framework of entropy and its Legendre transforms. So,  in the case of  microscopic description it is easier (more intuitive) to work with maximum principles.
A: I find this question very interesting, as it deals with crucial concepts, common misunderstandings and often-encountered unclear reasoning.
Part of the reply by Andrew Steane points to an answer (in the legend of his Fig. 17.3). Yet, on the other hand, I don’t feel that the demonstration that follows is fully appropriate or that it correctly addresses the issue (for example, the maximum entropy principle does not apply to a system that is not isolated).
An important thing to understand (often a source of misconception) is that each point of the curve of Fig. 17.3 represents the entropy of a system at equilibrium for different constrained values of some internal parameters. As a consequence, plotting a "trajectory" on such a curve doesn't actually define any specific process, it just represents "loci of equilibrium states" to borrow the words of Herbert B. Callen.
To be concrete I will take the nice example in the legend of Fig. 17.3 from Andrew Steane: a cylinder filled with an internal piston and some gas in each compartment. Assume the cylinder to be of constant volume and with adiabatic walls. If the position of the piston is changed reversibly, the entropy of the system stays constant. Now, whether the piston itself is adiabatic or not won’t change the following reasoning, but for simplicity I will fist assume that the piston is adiabatic; I will come back to the diathermal case afterwards.
Case of an adiabatic piston
Imagine that the piston is manipulated from the outside to fix it at various positions while keeping the overall entropy of the cylinder constant. This can be done for example by moving the piston very slowly in order to avoid that any turbulence builds up. During this process, work is either received by or extracted from the cylinder and the internal energy of the system changes. Now, there will be a position where the pressure applied on the piston on each side by the gas in each compartment will be the same. (As a side remark for later, note that in this scenario of an adiabatic piston, the temperatures of each gas in each compartment play no role and can be of any values, only their pressures are relevant.) If a new constrained state is to be reached from this initial state of balance pressure by reversibly changing the position of the piston to a new constrained position, the pressure in one of the compartment will increase whereas the pressure in the other compartment will decrease. (As a side remark for later, note that at the same time the entropy of each compartment will stay the same as no heat is transferred to any of the compartments.) Therefore, to reach this new state some energy has to be transferred to the system in the form of work to counteract the difference in pressure that builds-up and the internal energy of the cylinder will be increased. This shows that the state with equal pressures is the state of minimal energy.
Now, from any initially constrained position of the piston, imagine that the constraint is released. From the moment the constraint is released, we consider the cylinder to be isolated. If the piston is initially at the position of equal pressures (that is, at the position of minimal internal energy), nothing happens: for a system of constant entropy, the state of minimal energy is stable. If the piston is not initially at the position of equal pressures the piston will be spontaneously displaced by the difference of pressures and the system will be spontaneously pushed towards the state of minimal internal energy: for a system of constant entropy, the states that are not of minimal internal energy are unstable whereas, again, the state of minimal internal energy is stable.
This is where the equilibrium thermodynamics reasoning stops: stating which of the constrained equilibria is an overall equilibrium when some constraints are removed. If one were to compute what happens next and how the system would evolve, one would need to build a mechanical dynamic model of the piston moving inside the cylinder under the influence of the forces of pressure from the gases in each compartment. In the hypothesis of reversibility, this would give as solutions oscillating movements of the piston inside the cylinder around the position of minimal internal energy (thermodynamic equilibrium) –that is, around the position of minimal potential energy (because at thermodynamic equilibrium there is no macroscopic kinetic energy to be considered since the system is static). We see here the analogy of static equilibrium position between thermodynamics and mechanics.
Case of a diathermal piston
To be complete, let’s now assume that the piston is diathermal. This implies that for all constrained equilibrium states considered, the temperatures of the gases in each compartment are always equal to each other. If the piston, initially at a position of equal pressures in each compartment (and so here also of equal temperatures between the gases) is brought reversibly to a new constrained position, similarly as before the pressure in one compartment will increase whereas the pressure in the other compartment will decrease. The difference with the adiabatic case here is that at the same time heat will now also flow from one compartment to the other to keep both compartments at the same temperature. Note that the new temperature of the gases in the compartments may differ from the initial temperature, but the important point here is that they will stay equal to each other. This heat transfer corresponds to a flux of entropy between the two compartments, but the total entropy of the cylinder stays the same: since the temperatures of both compartments are always equal on reversible paths, one can write (hypothesis of reversibility): $dS = dS_1 + dS_2 = \delta Q_1/T + \delta Q_2/T$, which,  with $\delta Q_1 = - \delta Q_2$, gives $dS = 0$. So, similarly as for the adiabatic case, the total entropy stays constant, however, compared to the adiabatic case, there is no build-up of temperature difference here, and the total difference in pressure reached might not be the same as previously. Yet, from here the reasoning on the stability of the different positions of the piston when the constraint on the position is removed stays the same, and one finds that for a system of constant entropy the equilibrium position is the position of minimal internal energy.
Case of a diathermal cylinder in contact with a thermal bath
The above reasoning can of course also be followed in the case where the cylinder has diathermal walls and is in contact with a thermal bath that maintains the system at a constant temperature $T$. The crucial point here is that now, during a reversible process that moves the piston, there is also a flux of entropy between the cylinder and the thermal bath ($dS = \delta Q/T$, with $\delta Q$ the heat received (algebraically) by the system from the thermal bath), so the cylinder is not anymore at a constant entropy. If one would want to reason with a constant entropy, one would need to consider the total internal energy of the overall system composed of the cylinder plus the thermal bath. If one would want to reason only on the cylinder, neither the principle of maximal entropy nor the principle of minimal energy applies to the cylinder alone. To reason on the cylinder only, which is maintained at constant temperature, one can only reason on the Helmoltz free energy $F=U-TS$ of the cylinder. In this case, the equilibrium position of the piston would be the one with minimal Helmoltz free energy for the cylinder, over all the constrained equilibrium positions of the piston at constant temperature (vs the minimum of internal energy at constant entropy).
To explore those issues further, I suggest especially Problems 2.7-3 and 3.4-8 of Callen's Thermodynamics and an Introduction to Thermostatistics (note that 3.4-8 gives different results whether you consider a reversible or an irreversible process) and Problem 4.3-1.
A: 
This is figure 17.3 from Thermodynamics, a complete undergraduate course by myself (Steane), published by OUP (2016). Here is what I hope is an intuitive argument. 
For a $pV$ system, consider the situation at given $S$ (the volume $V$ being also fixed). Let $X$ be an internal parameter. The states at various $X$ have different internal energies to one another. Of these states, the one with the least internal energy is the equilibrium state when the system has the given $S$. 
Proof:

A: Equilibrium states are states that can be defined with just a few parameters like $V,T,S,P,N \text{ and }E$, that are related by an equation of state. So if you are defining an equilibrium state completely, there is only one such state. If any one of them are different, then they are two different equilibrium states.  
However, if you are referring to the many different internal states (microstates) that your system can be in that lead up to the correct macroscopic equilibrium state, then you are right about each such microstate being equally likely to be present.
A: Your wrote: "My intuition, however, says that if a system has a bunch of states available to it, and all states have the same entropy, then it should not prefer one state over the other and all of them should be equally good "equilibrium states"."
If I understand you correctly you are echoing Pippard's view $[1]$ of the maximum entropy principle. Let me quote from his magnificent book:

Now for any given set of constraints a thermodynamic system has only one true equilibrium state, and we may therefore formulate the entropy law in a slightly different way:
It is not possible to vary the constraints of an isolated system in such a way as to decrease the entropy.
When the gas is in equilibrium in the larger volume its density is very nearly uniform, but is subject to continual minute fluctuations. Very
occasionally larger fluctuations will occur, and there is a continuous
spectrum of possible fluctuations ranging, with decreasing probability,
from the very small to the very large; so that it is a theoretical
possibility (though it is overwhelmingly improbable of observation
even on a cosmic time scale) that the gas may spontaneously collapse
into the smaller volume from which it originally escaped at the piercing
of the wall. It will subsequently expand again to fill the full volume at
just the same rate as at the first escape. We may now inquire what happens to the entropy of the gas during this large-scale fluctuation,
and to this question the only satisfactory answer is the perhaps
surprising one-nothing.[...]

and the punch line(s):

Thus we see that the entropy (and of course other thermodynamic functions) must be regarded as a property of the system and of its constraints, and that once these are fixed the entropy also is fixed. Only in this sense can any meaning be attached to the statement that the entropy of an isolated mass of gas, confined to a given volume, is a function of its internal energy and volume, $S=S(U, V)$. It follows from this that when the gas is confined to the smaller volume it has one value of the entropy, when the wall is pierced it has another value, and that it is the act of piercing the wall and not the subsequent expansion that
increases the entropy. In the same way when two bodies at different
temperatures are placed in thermal contact by removal of an adiabatic
wall, it is the act of removing the wall and not the subsequent flow of
heat which increases the entropy.

[1]: Pippard: ELEMENTS OF CLASSICAL THERMODYNAMICS, pp. 96-98
