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.
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.
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.