storing energy (as mass) When chemical energy is released mass is reduced, if only by a negligible amount. Presumably that's true for all energy.  And presumably that works in reverse as well: storing energy involves an increase in mass. It seems to follow that moving some object against a gravitational gradient, increases the mass of the object -- potential energy is being stored.  Somehow that's difficult to understand. Is it really true?
 A: From your question and your comments on Google+, it appears you think there is a problem with having the increased energy stored in the gravitational field since the gravitational field is really just curved space-time.  That is not a problem, curved space time does have an energy density and in fact can cause additional curvature of space time. That is why general relativity is much more difficult than Newtonian gravity or electrostatics - the equations of general relativity are non-linear exactly because the energy stored in the curvature of space-time causes additional curvature of space-time.
In fact, John Archibald Wheeler conceived of the possibility of a gravitationally bound object that is only made from gravitational waves.  From Wikipedia:

Wheeler introduced the notion of geons, gravitational wave packets confined
  to a compact region of spacetime and held together by the
  gravitational attraction of the (gravititational) field energy of the
  wave itself. Wheeler was intrigued by the possibility that geons could
  affect test particles much like a massive object, hence the slogan
  mass without mass.

It is believed that a geon could be formed, but that the "particle" would dissipate due to gravitational waves that escape from the object, thereby reducing it's mass.
So, to get back to your question, two different configurations of particles that had the same total rest mass but different gravitational fields would, indeed, have different overall total mass/energies due to the different amount of energy stored in the differently curved space-times around the objects.
A: I'm explaining this for an electrostatic situation first, as gravitational potential energy is a strange concept in GR. The basic explanation should be the same for gravity, too, just that the formula may be different.
Let's take two positive point charges, and let's bring them together. So we did some work.. Where did the energy go? It wnt into the field (you'll find this written in many places as 'the configuration of the system'). And electric field requires energy to be generated. So, there is an energy density, $\frac{1}{2}\epsilon_0E^2$ associated with the field at every point in space. Integrating this formula with respect to dV will give us the energy enclosed in a certain area. So basically, this energy is spread throughout the universe (or atleast the local region). So if you draw an imaginary box near these charges (but not containing the charges), you will find that its mass-energy has changed. Even though the box has no massive particles in it.
One way of looking at this energy stored in an electromagnetic field is that it comes from the photons which mediate the field. Wherever there are field lines, there have to be photons which transmit the field. These photons have an energy, thus giving rise to the net energy density.
A similar thing exists for gravitation, though here the energy goes into the curvature of space. So no, moving a point body against a gravitational gradient does not increase its mass, but it increases the mass of its surroundings, however 'empty' the surroundings may be. If the body is not a point body, then its mass can change, as the field has some energy stored inside its volume as well. But this new mass won't exactly be part of the body's mass, it will just be in the same spot as the body. The rest mass used in the relativistic expressions will not change unless the body is heated by the change in PE (In this whole explanation, i have assumes an external force is moving the masses around. If there is heating involved, the masses will change due to the mass-energy equivalence)
Summing up, potential energy is stored in the field itself and not inside the masses that make up the field.
A: Let's say we have thousand identical masses spread around in space. These masses coalesce into one large mass, without any energy being radiated away, which means the large mass will become hot. Mass is conserved, so mass of the large mass equals thousand times the mass of one small mass.
Now one thousandth part of the large mass is winched up, so it's far away from the large mass, floating in space as in the beginning. It's like an original small mass, with some heat added into it. 
We want to know where the mass of the fuel of the winch went. Into the lifted mass went a mass that is equal to the mass of the heat energy.
Lifting the next chunk, identical to the previous one, will require one thousandth part less energy, because gravity field is now one thousandth part smaller. This energy came from the winch fuel, and was stored into the large mass. As there are 999 of these chunks, almost the same amount of energy that went into the small mass, went into the large mass. The exact ratio is 999/1000. 
EDIT:  Let's consider Alice, who holds a rope, and Bob, who descends into a gravity well, sliding along the rope, wearing gloves. The gravity field is homogeneous, so Alice will say that weight of Bob does not change. Bob will say that the gloves get hot, and their mass and weight increases. 
Now let's say Bob slides down so slowly that any extra heat is radiated away. In this case Alice will say that mass and weight of Bob decreases. Bob will say that his mass and weight do not change.  
If braking energy leaves Bob, Bob loses mass.
If Alice is lowering Bob into a well, mass moves from Bob to Alice. The reverse process of this is Alice pulling Bob up from a well, mass moving from Alice to Bob.
When Bob is descending, there is NO energy moving from anywhere into Bob, although physicists may so claim. Alice will confirm this. Bob's weight newer increases, during descending process, that's what Alice will say.
Here more about Bob and Alice
