First off, I'm sorry to hear and am surprised that you weren't accepted anywhere. How you weren't accepted anywhere is beyond belief. I agree with the poster above, maybe something was amiss with your application and perhaps you should e-mail the departments you applied to and the advisers and ask what weaknesses you may have had.
Secondly, I must admit that one of the writers of my LORs is very, very well known in his field and another one of my writers ran into two of the 5 profs who I wished to work for at a conference and talked me up. I think these connections helped me get accepted.
Lastly, when I applied, the paper I co-authored wasn't accepted yet. What I did was mention in my SOP that I had submitted a paper. I noted the title and journal publication as well. Funny thing was that the paper was rejected, so we submitted it to another journal and then it was accepted. As soon as it was accepted, I wrote in to all my potential advisers and the grad offices of the schools I applied to so that they could make a note of this.
I think when I mentioned to my potential advisers that I had a paper in submission, their interest was piqued and they encouraged me to apply. Of course having a paper in submission a huge step, having one published is even better. Either way, adcoms should realize that people (usually) don't submit a shitty paper and that you were involved in the science somehow. Your lab supervisor should note that on you LOR. I suggest you have a meeting with him/her to make sure you cover all the points you wish him/her to write on your LOR.