For a respectable journal (which I would assume an Elsevier journal to be), this behavior seems so weird and unacceptable that I am tempted to assume that you are only telling us parts of the story here.
Specifically, the part about "but they gave no real explanation for what happened" is curious - what was the reason they gave? This will very much influence the advise you get here.
If, for instance, they said that the previous accept mailing was sent out in error and the new reject notification is correct based on review results, well ... then it would definitely suck for you, but I see no way to fight this decision. You are then basically in the crowded boat of people that feel like their journal paper was rejected even though the reviews were not that bad. That you received an accept notification first does not fundamentally change this. I also do not share the hope of Ben Voigt that you could potentially sue for compensation - as far as I know, journals typically reserve the right to cancel publishing a manuscript at any point in the process, so legally they should be fine to change their mind even at a very unusually late point.
If they said that they have in the meantime learned that parts of your paper are already under copyright elsewhere, then you can either clear up the misunderstanding (if it is one) or alternatively propose to revise the paper.
If they really give literally no useful explanation (don't answer your mail, or answer with no actual information), then I would fall back to the answer of Wrzlprmft and contact Elsevier.