How can I use a magnet to lift a paperclip? This question  has been asked already, but no satisfying answer came up. All the answers seem to push the problem further, but do not explain clearly what is going on.
I will reformulate it for a specific case, tell you what I have gathered from the answers and what specifically I am expecting.

Setup: I have a powerful ferromagnet, and a paperclip lying on the table. I touch one pole of the ferromagnet to the clip, then lift the whole thing. The paperclip comes up with the ferromagnet.
When I pull on the ferromagnet, I am applying a force on it, thus doing work on it, providing the energy to lift both the magnet and the clip up the potential well.

The problem: The paperclip though experiences the pull of gravity and the pull of not of my hand, but the pull of the magnetic field. It seems to me the magnetic field is doing work on the clip.
However, the Lorentz force caused by a magnetic field on a moving particle is always perpendicular to the motion, so does no work. This is true also for constrained motion. The magnetic field cannot do work on the atoms of the paperclip.
So here we are. A paperclip is made of charged particles: electrons and nuclei. Magnetic fields cannot do work on charged particles. However, there is an undeniable attractive force on the paperclip by the magnet, and this force is capable of lifting it in a potential well, so it does work.

The answer I am looking for:
It seems to me that in the paradigm of classical mechanics + Lorentz forces + point-like charged particles this question has no consistent answer.
Two options:
1) You can prove me wrong, by showing me clearly how can the magnetic field of the magnet do work on an assembly of particles.
2) If I am right, then I would like to see what further notions are necessary  $-$ be it treating the electrons as currents and using Maxwell's eqs or introducing quantum spins. I also want to see how these new concepts imply that the field from a magnet can do work on a piece of metal.
NB: you are allowed to treat both the paper clip and the magnet as infinite in extent in two of three spatial dimensions.
 A: The important thing here is that a magnetic dipole, like a permanent magnetic or induced magnetism in ferrous material, produces a nonuniform field.
The potential energy of a magnetic dipole $\vec\mu$ in a magnetic field $\vec B$ is 
$$ U = - \vec \mu \cdot \vec B .$$
Most frequently (as in anna v's answer) this is used to explain the torque which causes the magnetic moment to want to align with the external field: the energy is minimized if $\vec \mu$ and $\vec B$ are parallel.  Let's suppose they are aligned already; we find the force as
$$ \vec F = -\nabla U.$$
However the gradient of a scalar product has a surprisingly complicated expansion, which you can verify by expanding all the component terms.
$$
\nabla(\vec \mu\cdot \vec B) 
= (\vec\mu \cdot \nabla) \vec B
+ (\vec B \cdot \nabla) \vec \mu
+ \vec \mu \times (\nabla \times \vec B)
+ \vec B \times (\nabla \times \vec \mu)
.
$$
We can simplify this by consider $\vec\mu$ constant, so those gradients go away.  From Maxwell's equations we have $\nabla\times\vec B=0$.
Finally let's define our coordinate system so that $\vec\mu$ (and therefore $\vec B$, since we already assumed they are aligned) point along the $z$-axis.
That leaves us with 
\begin{align}
\vec F 
&= (\vec \mu \cdot \nabla)\vec B
= \left(\mu \frac{\partial}{\partial z}
\right) B_z \hat z
.
\end{align}
So for a permanent dipole $\vec\mu$ in a field $\vec B$ we find three limiting cases:


*

*If $\vec \mu, \vec B$ are parallel, the dipole will feel a force in the direction of increasing $|B|$

*If $\vec\mu, \vec B$ are antiparallel, the dipole will feel a force in the direction of decreasing $|B|$

*If $\vec\mu, \vec B$ are not parallel, the dipole will feel a torque that makes it want to align with the field.
This is pretty much my experience with permanent magnets.  To get permanent magnets to repel, you have to constrain their rotation somehow; what they like to do is to flip around and attract.  Induced magnetism (e.g. paperclips) is the result of many microscopic aligning torques.
You can find the same result by noting that the energy stored in a volume element of magnetic field is $dU = (\vec H \cdot \vec B) d^3x$, and finding the arrangement of magnets which minimizes the volume of strong field.  This is relatively intuitive for parallel dipoles aligned end-to-end, which have a strong field in the empty space between the magnets, and also for antiparallel dipoles set side-to-side, where the "return fields" between the dipoles add.  To see the repulsive cases, though, you have to do a messy integral over the fringe fields to confirm that the distant-dipole configurations have less stored energy than the near-but-not-overlapping-dipole configurations.
As for the argument that the Lorentz force 
$$
\vec F = \frac{d\vec p}{dt} = \frac qm \vec p \times \vec B
$$
can do no work, because the force is perpendicular the the momentum and therefore cannot change the magnitude of $|p|$: this argument assumes that the field $\vec B$ seen by the particle is uniform.  If $\vec B$ varies along the particle's path, the particle (in its rest frame) sees a time-varying $\vec B$ and an electric field which obeys $-\frac{\partial\vec B}{\partial t} = \nabla \times \vec E$.  It's the induced electric field that does the work.  There's a nice problem in Griffiths's E&M textbook that works through the argument.
A: I would like to add a supplement to the accepted answer.  The accepted answer is an excellent derivation based on physical principles, but after reading it, I couldn't help but feel that the answer is much more abstract than the question.  This makes it feel like the mystery is being moved from the original question "How can magnetic forces do work?" to "Why is the potential energy of a magnetic dipole given by $-\vec{\mu} \cdot \vec{B}$?"  Now, of course it is possible to address the latter question in a variety of ways (for example, one could take this answer for a current loop, and then make the loop infinitesimally small).  However, I want to address this issue from a purely intuitive point of view and use nothing but the Lorentz force and Maxwell's equations.
Before I begin, I want to comment that multiple answers both here and elsewhere have addressed the fundamental issue, which is that a dipole is not the same as a charged particle.  (Speaking very loosely, a dipole can be imagined as a current, or multiple moving charged particles, whose net electric charge is zero, and which are stuck in a certain configuration.  So one can attribute the "work" done to whatever forces hold the dipole together, or, depending on the case considered, to forces that hold a collection of dipoles together, or to other forces specific to a particular situation.)  Although this clearly indicates the fundamental error in the argument, it still does not give a concrete mental picture for how the Lorentz force leads to the work being done.
Intuitive Argument
For simplicity, imagine that a bar magnet consists of a collection of magnetic dipoles that are all parallel to the $z$ axis.  Each of these magnetic dipoles can be replaced by an infinitesimal current loop, so it is reasonable to imagine the entire magnet replaced by one large current loop in a plane defined by $z=\textrm{const}$.  This gives us the benefit of imagining the magnet as a collection of moving particles, so that we can refer to the Lorentz force.  The simplest model of such a current loop is a resistive wire attached to a battery.
Instead of considering the interaction between this current loop and a paper clip or a second bar magnet, let's simplify the problem by postulating that there is an external, time-invariant magnetic field whose source is far away.  The question is whether this magnetic field can do work on the current loop.
Consider three cases:


*

*The external magnetic field $\vec{B}$ has a component that is not in the $z$ direction.
In this case, it is very easy to draw a picture and confirm, using the Lorentz law, that the loop will typically experience a net force or a net torque and, therefore, work will be done on it.  This is explored quantitatively here.


*

*Consider the case where the loop is a circle and $\vec{B}$ contains a component that goes radially outwards.  There will be a net force in the $z$ direction.

*Consider the case where $\vec{B}$ is uniform.  There will be a net torque but no net force.


*The external magnetic field $\vec{B}$ is parallel to $z$, but varies in value throughout space.
This is a violation of Maxwell's equations, which require $\vec{\nabla} \cdot \vec{B} = \frac{\partial B_z}{\partial z} = 0$.  So, we can ignore this case.

*The external magnetic field $\vec{B}$ is parallel to $z$ and uniform.  In this case, there is no net force nor a net torque, so there is no mystery to be explained.
Additional Comments
There are a couple of details that writing the argument above forced me to consider.
More details on case 2
First, the interpretation of case 2 can be somewhat more complicated than what I wrote above.  This is due to the idealization of the wire as being one-dimensional.  One could arrange the wire so that, on the wire, $\vec{B}$ is parallel to $z$ and has constant magnitude, but $\vec{B}$ depends on $x$ and $y$ so that $\vec{\nabla} \cdot \vec{B} = 0$, and $B_z$ changes off of the wire.  (I am not entirely sure whether constructing such a $\vec{B}$ that globally satisfies $\vec{\nabla} \cdot \vec{B} = 0$ is possible, but I am assuming for the moment that it is.)
The force in this case would be the same as case 3, i.e.,
$$\vec{F} = I \oint \left( d\vec{\ell} \times \vec{B} \right) = I \left( \oint d\vec{\ell} \right) \times \vec{B} = \vec{0},$$
since $\vec{B}$ is constant along the path of integration.  A similar argument shows the torque to be zero.  So, once again, there is no mystery to be explained.  Note that, for an object with finite volume, the situation described in this paragraph would probably be categorized as part of case 1.
Relation to the model of a dipole as an infinitesimal wire loop
Another point to consider is how the types of arguments presented in this answer relate to the expression given for an infinitesimal dipole in the accepted answer.  There, for a dipole with $\vec{\mu} = \mu \hat{z}$, the force on the dipole is given by $\mu \partial_z B_z \hat{z}$.  However, in the last paragraph I admitted that, at least for a finite loop, it may be possible to come up with a magnetic field where similar conditions are met, but the force is zero.
The key here is to realize that, for an infinitesimal dipole, Maxwell's equations put a very strong constraint on the relationship between $\partial_z B_z$ and the other field components along the wire.  For simplicity, take the case where the wire is a loop of radius $a$ in the plane $z=0$ and we will be interested in taking the limit where $a$ is very small.  In the center of the loop, $\vec{B}(\vec{0})=B_0 \hat{z}$.  eMoreover, assume that the magnetic field is radially symmetric.  I will use cylindrical coordinates and suppress $\phi$ (due to symmetry) and $z$ (because we are only interested in the plane $z=0$).  On the loop, the field has the form
$$ \vec{B}(a) = \left( B_0 + a \partial_r B_z \right) \hat{z} + a \partial_r B_r \hat{r} $$
The derivatives are all evaluated at $\vec{0}$.  Now, the $z$-component will not contribute a net force, as discussed above, but notice that there may be a radial component, which we know can cause a net force on the loop.  We get
$$ \vec{F} = \oint d\vec{\ell} \times \vec{B} = I \int_0^{2\pi} ( a d\phi \hat{\phi} ) \times ( a \partial_r B_r \hat{r} ) = -2 \pi a^2 I \partial_r B_r \hat{z} = -2 \mu \partial_r B_r \hat{z} $$
The critical observation is that $\vec{\nabla} \cdot \vec{B} = 0$ implies that $\partial_r B_r = -\frac{1}{2} \partial_z B_z$.  So the expression above becomes
$$ \vec{F} = \mu \partial_z B_z \hat{z} $$
which was derived above.
The point is that Maxwell's equations require that you cannot have a nonzero $\partial_z B_z$ without also having a nonzero derivative for other components of the magnetic field, and we have already seen how the other components can cause a force in the $z$ direction.
A: It is an experimental fact that atoms and molecules have magnetic moments. Also elementary particles with spin have magnetic moments as well as protons and neutrons.
It is not classical mechanics that will describe the behavior  of atoms and molecules, but Quantum mechanics.
Quantum mechanical theoretical models of magnetism exist, and early on in the history of physics for  ferromagnetism .

So they are not really new concepts, but as old as quantum mechanics.
Edit to reply to:

A paperclip is made of charged particles: electrons and nuclei. Magnetic fields cannot do work on charged particles.

But they can do work on magnetic dipole  moments.

However, there is an undeniable attractive force on the paperclip by the magnet, and this force is capable of lifting it in a potential well, so it does work.

A magnetic potential can  be defined macroscopically .

A magnetic dipole moment in a magnetic field will possess potential energy which depends upon its orientation with respect to the magnetic field. Since magnetic sources are inherently dipole sources which can be visualized as a current loop with current I and area A, the energy is usually expressed in terms of the magnetic dipole moment:



The energy is expressed as a scalar product, and implies that the energy is lowest when the magnetic moment is aligned with the magnetic field. The difference in energy between aligned and anti-aligned is



The expression for magnetic potential energy can be developed from the expression for the magnetic torque on a current loop.
These relationships for a finite current loop extend to the magnetic dipoles of electron orbits and to the intrinsic magnetic moments associated with electron spin and nuclear spin.

However, there is an undeniable attractive force on the paperclip by the magnet, and this force is capable of lifting it in a potential well, so it does work.
A: It's true that the Lorentz force can do no work. As others have pointed out, a non-uniform magnetic field can do work on intrinsic dipoles. I feel something else should be pointed out, too: the magnetic field can do work on the electric field, which then does work on charged particles. See: the phenomenon of magnetic induction where a changing magnetic field produces an electric field which does work.
