Made an arXiv submission too early; How to minimize the damage? A confession first: This was our first attempt at a journal paper. 

The story so far:
We had submitted our work for possible publication with a reputed journal in our area. Some time later, while the review was still on, I checked out whether this journal allowed self-archiving of author's version of the paper. Feeling glad that it did (and being quite confident that our paper will get accepted), we decided to upload our pre-print on arXiv. 

And now...
The decision arrived from the journal. It was a reject. Amongst the other things written by the reviewers, one of the points happens to be: 


  ...I am a bit concerned with what appears to be the same paper
  published and made available from: arxiv.org/xxx/yyy. I would
  recommend that the authors clarify this potential duplication.


I do not think that this was the only reason for rejection, but might have contributed to it. 

My questions:
I know I did a mistake due my lack of awareness of the proper rules. How to rectify my mistake?
Should I consider that this work of mine cannot be published to any conference/journal since its pre-print happens to arXived already?
As far as I understand, arXiv does not allow us to remove papers. I can request a withdrawal, but even then the previous version(s) will remain available online (for any future reviewers to bug us).   

What is the best course of action for me?



update based on answer by @F'x:
Adding this from the Journal's website, Guide for authors page:


  Copyright is retained by the Publisher. Submission of an article implies that the paper has not been published previously; that it is not under consideration for publication elsewhere; that its publication is approved by all authors and tacitly or explicitly by the responsible authorities where the work was carried out; and that, if accepted, it will not be published elsewhere in the same form, in English or in any other language, without the written consent of the Publisher.
The answer to your question depends on the exact details of the journal's policy (and it would be good for you to quote them exactly, or give us a link). More precisely, it depends not only on the journal's policy regarding self-archiving, but more importantly on the journal's policy on prior publication.

I know that might sound weird, but these are actually two separate questions. Self-archiving is a question of copyright, a legal issue: it's a question of what rights you retain (and what rights you transfer) according to the agreement you have with the journal's publisher. This copyright agreement is not something that influences the peer review process, it only governs what you agree with the publisher should they actually accept to publish your paper. (The agreement is void if the paper will not be published, obviously.)

Now, the journal's policy on prior publication is not a legal issue, it is a question of scientific (or editorial) policy. It is decided by the journal's editorial board, and should be explicitly spelt out in its guidelines for authors, journal policies or another similarly titled document. Some journals, like those of the American Chemical Society, have a very strict policy on prior publication:


  The Journal of the American Chemical Society considers for publication only original work that has not been previously published and is not under consideration for publication elsewhere. When submitting a manuscript, an author should inform the editor of any prior dissemination of the content in print or electronic format. This includes electronic posting of conference presentations, posters, and preprints on institutional repositories and any other Web sites. Any content that has been made publicly available, either in print or electronic format, and that contains a significant amount of new information, if made part of a submitted manuscript, may jeopardize the originality of the submission and may preclude consideration for publication.


Thus, this journal would reject any manuscript that was posted on arXiv (or anywhere else), because it is not considered original material.



Now, what about you? Well, you have to find out what your journal's policy is, and act accordingly. If the journal policy forbids prior publication, then accept that you made a mistake, find a journal that doesn't have such requirements (it depends on fields, but it should not be too difficult), and submit it there.

On the other hand, if the journal policy does not forbid such prior publication, then you only made a smaller mistake: not informing the editor. Thus, if you want to appeal the rejection, you may want to write an apologetic letter to the editor with that information (along with answering the other comments of the reviewers). As you say that this was not the main reason for the rejection, I wouldn't advise appealing though (chances of success are very slim).