How could Adam and Eve lose their just standing before God if it was given to them as a Grace and not earned? I have often heard pastors, internet preachers especially, repeat that, "We did nothing to earn our salvation and there is nothing that we can do to lose it" or something to that effect. These are generally pastors who accept the doctrine of eternal security or Once Saved Always Saved.

I believe we can agree that our first parents, who were in a state of original justice, had done nothing to earn that initial state and that it was a gift of God by virtue of his perfect creation. But if they had done nothing to earn their state of justification before the fall, how is it that they could lose it?

I'm scoping this question to those who accept Once Saved Always Saved and believe in the historicity of Adam and Eve as the original parents of the human race.
Reformed Protestant theology, which includes the doctrines of justification by faith alone and the perseverance of the saints (the inability to lose said justification) regard salvation to be necessary for mankind as a result of the sin of our "first parents". 

That is to say, Adam and Eve did not receive "salvation" nor were they "justified" before the fall, because justification refers to the forgiveness of transgressions and the restoration of right standing with God, and salvation refers to that from the wrath of God that results from sin and is accomplished solely by the atoning work of Messiah. Adam and Eve did not "lose" salvation by their sin- they had not received salvation because before their sin, there was no condemnaiton from which they required salvation and no atoning sacrifice was called for. Likewise, they had not been justified because they, unlike their descendants, were not in a state where they were separated from God because of sin but alternatively already occupied the very state of perfection to which justification restores the sinner. 

From Luther's commentary on Genesis 3:


  In the preceding chapter [of Genesis], we were taught the manner in which man was created on the sixth day; that he was created in the image and after the likeness of God, that his will was good and perfect, and that his reason or intellect was also perfect, so that whatsoever God willed or said, that man also willed, believed and understood... Universal experience indeed shows us all these calamities [caused by the fall]; but we never feel the real magnitude of them until we look back to that unintelligible but real state of innocency,
  in which there existed the perfection of will, the perfection of reason and that glorious dignity of the nakedness of the human body. When we truly contemplate our loss of all these gifts and contrast that privation with the original possession of them, then do we, in some measure, estimate the mighty evil
  of original sin... 
  
  Wherefore, as I said, let us never extenuate, but rather magnify that
  mighty evil, which human nature has derived from the sin of our first parents; then will the effect he that we shall deplore this our fallen state and cry and sigh unto Christ our great Physician, who was sent unto us by the Father for the very end that those evils, which Satan has inflicted on us through sin, might by him be healed, and that we might be restored unto that eternal glory, which by sin we had lost. 


To utilize Luther's analogy, salvation and justification are the forms of healing and results of the treatment of our Divine Physician, Jesus Messiah. Before the fall, Adam and Eve were not saved or justified, but they were perfectly healthful in both the physical and spiritual sense, not yet requiring the work of that Physician until after sin had inflicted upon them its grave injury. 

So, to say that Adam and Eve lost salvation or justification in the manner of speaking meant by the doctrine of the perseverance of the saints or to ask how such were lost is to commit a categorical error. It is only after the fall that the human race needed to be saved from the incurred wrath and restored into right standing with God.