So the law is the prediction, and the theory explains the law. An interesting way of looking at it.
I'm not sure there's such a difference between Newtonian and Einsteinian gravitation. Einstein may have attributed to the curvature of spacetime, but the problem still exists: why does mass bend spacetime? In that regard, Newton's 'laws' are as much of an explanation as Einstein's.
		
		
	 
Hmm... that's a good point.  I still do think that theories involve explanations, whereas laws are just statements or equations... perhaps there's a theory or theories that were developed based on Newton's law of universal gravitation, and laws that are behind general relativity.
Albert Einstein - Wikipedia, the free encyclopedia
The theory of general relativity has two fundamental laws  the Einstein equations which describe how space curves, and the geodesic equation which describes how particles move.
This paragraph calls the equations "laws," anyway.  Perhaps they haven't been elevated to the status of laws, though.
In the case of general relativity, the theory was developed before the Einstein field equations were found... I think.  I'm not sure what it specifically means by geodesic equations.  Anyway, the theory builds upon the laws/equations, explaining their consequences.
A theory based on Newton's law of gravitation might then be explanations of its consequences, such as how it explains the motion of the planets... I'm just kind of guessing here, though.
Still, in a way, there is a difference between the two in terms of how gravity is explained.  Newton's law of gravity requires a force, and the particle that transmits this force was not known at the time -- they didn't have a clue (we have some theories about what it might be, now).  But with general relativity, there is no force required to transmit gravity, and therefore no hypothetical particle.  It's true that there really isn't an explanation for *why* mass/energy/momentum bends space-time in general relativity, but we do have equations that describe how it happens.
Whenever we do find an answer to "why" something happens in physics, you often end up on even more questions... for example, in trying to understand the properties of protons and neutrons, you find out that they are made up of up and down quarks, which have certain properties that explain it (spin, mass, strong and weak nuclear forces).  But then you can what quarks are made of, or why they can convert from one type to another, and ask why they have those certain properties.
There's a phrase that describes this process, but I don't remember what it is.
So, to summarize... yeah, I'm not terribly sure, myself.  The Wiki article on Newton's law of gravitation flip-flops between calling it a law and a theory.  I think the law would tend to be without all the extra detail explaining its consequences, though.