Thank you! You have no idea how much that means to someone whose first experience with asking this question was to get into trouble with the teacher for “causing trouble” (AKA “asking a question the teacher can’t answer”) 
Nope. Pasta and Q.E.D. have it right; the potential energy is a property of the system in toto, not of the component parts even as divided. The supposed paradox in the o.p. highlights this, insofar as the two boulders being essentially indistinguishable by themselves (differences in weight from their distance from Earth notwithstanding).
To pose the issue another way, take one boulder massing 1,000kg and accelerate it to 10,000 m/s, giving it a kinetic energy of U = 0.510[sup]3[/sup] kg(110[sup]4[/sup] m/s)[sup]2[/sup] = 5.010[sup]10[/sup] J for an inertial observer, i.e. one not accelerated with the rock. Take another 1,000 kg boulder and accelerate it to 20,000 ms; the kinetic energy of this boulder is U = 2.0*10[sup]11[/sup] J, i.e. four times as much kinetic energy, again with respect to the static observer. However, an observer on one boulder and not referencing anything else would report that the boulder has the same mass, thermal energy, and other properties as the observer on the other boulder. The energy, kinetic or potential is a property of the boulder and inertial reference frame system but not any independent component of it.
Stranger
ftg, the OP is working in a Newtonian framework, and the conservation of energy is valid within it. I’m not sure that invoking relativistic ideas (correctness notwithstanding) will do much to address his worries, as it simply dodges the question at hand, namely, why does (Newtonian) energy conservation seem weird, and what’s up with (Newtonian) potential energy. The Newtonian answer could be (IMHO) considered subtle.
To add another example here, consider the classic two photon situation. A system of two photons moving back-to-back has a finite mass. But, if you draw a box around one of them and call that your closed system, you will find that that photon has zero mass.
ftg, as Stranger and QED have already pointed out potential energy is a property of the system. So, even though the boulder itself doesn’t gain any mass the system consisting of both the earth and boulder does.
OK, I think I am starting to get the drift.
Firstly, to those who said “the rooms aren’t identical because one’s on a hill”, I kind of thought it was implied that I was setting up an experiment where I could say "These things are identical EXCEPT FOR this one thing… " Let’s not get hung up on the semantics, folks.
I get the feeling that my thought experiment, which seemed so elegant and perfect when I wrote it this morning, is deeply flawed. But it’s Sunday and I am feeling lazy so I don’t feel like making a new one. 
So what people are saying is, the boulder by itself has no potential energy (other than as mass), it only has potential energy relative to the system it’s in (to put it crudely). You might not be able to run your tricorder over it and “detect” the potential energy, but you could, with sufficiently sensitive instruments, detect the slight difference in mass and hence deduce which boulder was which.
I think part of my problem is I am trying to make this all make sense to a common-sense, as-you-see-it mindset of the world, where you can point to a thing and call it by name, and if you can’t, it doesn’t exist. Lots of forms of energy fit just fine into that mindset. You can measure heat with a thermometer, light with a light meter, and so on. Potential energy does not fit simply into this sort of thinking. “Show me the energy!” I am saying.
But this question’s explanation is a layer or two more subtle than that form of thinking can allow.
Now, some individual replies.
Well, none of them have been scientists professionally, although some of them were science grad students. However, the idea that only a scientist could answer my question is absurd. They needn’t be a Real Professional Scientist©, they just need to know more and understand more than I do, which is not too hard, as I am, at best, a dilettante theoretician in science.
You mention that you are still composing replies, but in the meantime…
This is incorrect. With a properly constructed thought experiment (which yours would be if the gravitational field were uniform), you would not be able to tell the boulders apart no matter what. They are identical.
First of all, I think your screen name is absolutely brilliant and once more makes me feel like I am the Dullest Man in the World for just using my actual name.
Secondly, migosh, anyone who references Wile E. Coyote in a science discussion has already got my vote.
And lastly, thanks for your reply!
Potential energy, like everything else, is contextual. Nothing exists independent of its environment and circumstances. So you can say of the two boulders: IF they are both at the top of the hill, or IF they are both at the bottom of the hill, or IF they are both hit by the same giant pool cue, or IF they are both blown up by identical sticks of dynamite, applied the same way . . . then they will act identically. If you put them both into the same context, they will act identically. The fact that you have put them in different contexts doesn’t change that.
I’m not a scientist.
But does this example help?
Take two cars (same model).
One is parked and you stand on its roof.
Meanwhile a pneumatic cannon (as demonstrated on Top Gear), placed right next to your good self, fires the second car directly upwards.
Consider the precise instant that the second car stops moving upwards (due to gravity).
Both cars are now stationary relative to you.
However the potential energy of the car in mid air means you will move very swiftly out of the way!
This has left me a bit confused.
Here is my understanding and I am curious if I am missing something:
An object moving relative to an observer has a greater mass than the same object were it stationary. (mass approaches infinity as velocity approaches c?) Wouldn’t it be correct to say that on the scale of men and rocks relative velocities are so small that this change in mass is essentially zero?
whoops, meant to preview, and hit submit instead… hold on
As others have said, let’s not muddy the waters with relativistic reasoning; it is sufficient to explain the significance of conservation of energy in the Newtonian framework.
To the OP: You are, to some extent, correct that “potential energy” is just a bookkeeping trick. But, then, all quantities in physics are bookkeeping elements, of some sort or another; such is the nature of numbers.
The question, then, is how does “energy is always conserved” remain a significant statement in the context of this accounting move; if we define “total energy” not merely as traditional kinetic energy, but instead add on this mysterious “potential energy” in order to allow us to say that total energy has been conserved, then have we not made conservation of energy an empty tautology, true merely by definition? Have we, in the end, claimed nothing non-trivial at all?
The answer will be “No, we do claim something non-trivial about the laws of physics”. The catch is that the non-triviality is entirely in one all-important, but easy to gloss over, realization: that we can define the potential energy of a system in such a way as that it depends only on the positions of the objects in that system, and not on their velocities [as would normally be required to determine kinetic energy].
I.e., the non-trivial claim we make is this: any two ways to get from position-configuration A to position-configuration B will bring about the same change in kinetic energy.
Having made that non-trivial claim, we can then do the trivial things: simply define “change in potential energy” as the negation of change in kinetic energy, so as to cause change in total energy to always remain 0. And then, having a notion of “change in potential energy”, all we need to do is pick an arbitrary zero-point in order to get a notion of “potential energy” itself. This part is indeed trivial. But, as I said, the important, non-trivial aspect is that the resulting notion of “potential energy” ends up depending solely on positions and not on velocities. That is what makes this significant.
The easiest way to see that this is last part is non-trivial is to illustrate what it would mean for it to be violated: suppose there are two possible ways for the rocks on the top of a hill to be moved to its bottom; in the first way, the total kinetic energy goes up by 3. In the second way, the total kinetic energy goes up by 5. In this case, it would be impossible to define “change in potential energy” of a position-configuration so as to exactly counterbalance change in kinetic energy; it would have to be both -3 and -5.
It is a non-trivial, empirically discovered fact of physics that rules out possibilities like the above; there is precisely one change in kinetic energy possible in moving between any two given position-configurations. And because of this, it is possible to define a coherent notion of change in potential energy precisely counterbalancing change in kinetic energy. That is the interesting fact that makes this something more than circularly defining things into truth.
Please mentally remove the bolded word; it obviously shouldn’t be there.
Quoth Pasta:
Incorrect. Potential energy gravitates, just like any other mass.
Quoth John H:
Also incorrect, at least under the currently-used definitions. The mass of an object doesn’t change with velocity. The total energy does, but the currently-used definition of “mass” is that it is the portion of the energy of a system which is invarient. Incidentally, using this definition, the mass of a closed system is always absolutely conserved: It only appears not to be when you’re sloppy about how you define your system.
So lets say we’re building boulders for this experiment. We build the boulder that goes on top of the hill with a little less mass so that it’s mass placed on the top of the hill equals the boulder at the foot of the hill.
Any change in the difference in potential energy between the two boulders?
I agree (as do Ring, Q.E.D., and Stranger upthread) that potential energy adds to the mass of the system. If you were allowed to measure properties of the entire system you could tell the two cases apart. But I don’t think this potential energy affects any locally-measurable properties of the boulder. The boulder’s mass, measured locally, will be the same in the two cases, right?
Perhaps we are talking about two different situations for the boulder. I’m envisioning the OP’s thought experiment, where the entire closed system is “small room + boulder”. I agree that the Earth+boulder system taken as a whole has a larger mass when the boulder is atop the hill, but an observer limited to the confines of the small room cannot measure this. I posit that such an observer cannot determine the proximity of the (say) infinite sheet of mass causing the uniform gravitational field.
Energy is stored as mass?
I am finding it hard to imagine this.
I’m used to thinking of the mass of the object as being a function of its density and how much of it there is. You only get more mass if you add more stuff.
But now, folks are saying the object in question somehow “stores” energy as mass? There’s the same numbers of moles of the same elements and yet, somehow the mass has changed?
This is hard to conceive, although I’m willing to beleive it. A lot of things which are true make no sense, in an everyday sense. Like, most of quantum physics.
Also, how would it change my thought experiment if the two identical boulders were not on Earth, but in space? And the only difference now is that one is orbiting a massive gas giant and the other is adrift in the interstellar void?