First of all, energy is energy. It may be converted from any form to any other form and there is absolutely no ambiguity about the sign of any form of energy. If $E$ is correctly defined so that it is conserved, the signs in front of all quantities are well-defined.
Your observations about $E^2$ and $B^2$ having the opposite sign in the Maxwell Lagrangian are correct, too.
However, what's incorrect is your assumption that the energy carried by a configuration of electric charges or dipoles or magnetic dipoles may always be reduced to the energy carried by the electromagnetic fields only, $(E^2+B^2)/2$.
This statement is kind of coincidentally true in the case of the electrostatic energy. The energy between charges, an integral of
$$\frac 12\int \rho \Phi$$
where $1/2$ is included to avoid double-counting from the interaction energy of pairs of charges - may be integrated by parts, using $\rho = \nabla\cdot E$ and $E=-\nabla \Phi$, to get
$$\frac 12 E^2$$
That's nice and if one manages to subtract the divergent self-interaction energy of point-like charges (which has been a big puzzle in classical physics and became an equally big puzzle in QED, before it was solved and superseded by renormalization), everything is stored in the electrostatic field energy $E^2/2$.
However, this is simply not the case for the magnetic fields. The actual energy is given by terms like $-\vec m\cdot \vec B$, as you correctly write. In particular, two equally oriented magnetic dipoles, separated by an interval in the same direction as the direction of these dipoles, have a negative interaction energy, see
http://en.wikipedia.org/wiki/Magnetic_dipole-dipole_interaction
That's why the force between two such dipoles is attractive - and the very same thing with the same signs would hold for two electric dipoles, too. The term $-\vec m\cdot \vec B$ may be boiled down to the $\pm\vec j\cdot \vec A$ in the Maxwell Lagrangian with sources. I wrote $\pm$ because I don't want to spend lots of time by fixing this sign because only some relative signs really matter for this question.
Now, mimicking the electrostatic integration by parts here in magnetostatics, $\vec j = {\rm curl} \vec B$ and $\vec B = {\rm curl} \vec A$, won't quite work because
$$ \vec j\cdot \vec A = {\rm curl} \vec B \cdot \vec A \neq - \vec B \cdot {\rm curl} \vec A +{\rm curl} (\dots). $$
Those curl identities don't seem to work in the same way. So the energy of magnetic dipoles can't completely eliminate the non-$B^2$ terms, I think.
Even in the electrostatic case, we have to be careful how we interpret the different energies to avoid double-counting. Because the $\int\rho\Phi/2$ energy could have been rewritten as $\int E^2/2$, we may imagine that charges are some mysteriously compact lumps of electric field. But aside from the $1/2$ factor that was needed to avoid the double-counting from the electrostatic energy of each pair of charges, there is one more dangerous place where we could double-count: we must either imagine that the energy comes from $\rho\Phi/2$, or from $E^2/2$, but not from both! Again, if we wanted to include both terms, they would have to have the same sign, and we would double the energy relatively to the correct value.
The magnetic counterpart is that we may express the energy density as $B^2/2$ if we don't study how the dipoles and sources are affected, but if we do, we must forget $B^2/2$ and correctly calculate terms such as $-\vec m\cdot \vec B$.
By the way, the problem with the sign would occur even for randomly generated electric dipoles. It's because $\int E^2/2$ is positively definite - for any configuration of dipoles - while the interaction energy between two dipoles may be both positive and negative. So it's just not true that the interaction energy of two ordinary dipoles may be rewritten as $\int E^2/2$. In some sense, the problem does reside in the dipoles' self-interactions.
Note that $\int E^2/2$ is always positively definite - so how it can account for the electric charges' interaction energies that can have both signs? The answer is that $\int E^2/2$ should be identified with $\int \rho\Phi$ plus the "internal mass" of the electric sources - which is basically infinite. However, $\int B^2/2$ is also positively definite while there is significant extra mass (interaction self-energy) associated with the magnetic dipoles themselves. So for the magnetic sources, exactly because the currents may be "light", the transcription into $\int B^2/2$ cannot work.
When we have either electric or magnetic dipoles, we must carefully put the right sign in front of the energy, instead of assuming that the energy may always be rewritten as "field-only" energy. It can't.
