My sole experience with Fiverr was terrible. I paid $35 to their highest-rated logo designer, who promptly delivered the worst logo I had ever seen. I'm not usually one to complain, but I was so unimpressed that I told the seller that I was not happy with the logo. His response was basically "I don't care. See ya!" I will never use Fiverr again. I've had much better luck with Elance.
Fiverr is worth trying again but next time use it for non-creative work. Also, don't allow yourself to get up-sold initially, keep things at $5. Toss a few fivers around and experiment. Like any network of people, you'll have some terrible participants and also great ones.
BTW - out of curiosity, would you care to link to the logo?
Edit: reading more about copyright infringement of designers on fivver. This is a huge problem. I would stay away from any creative work from anyone on fivver, regardless of their rating. Especially for something as critical as a logo.
Also note that most stock photo companies specifically say that you can't use their images in logos so you can't even buy the stock photo if you're comfortable with the stock photo as the logo.