In the final analysis, it really is a good pairing of playlist and audience that matters most. People want to hear their favorite songs played in an appreciable way.
Here's the tricky part, and where a lot of bands go south. You can take that "make it our own" mentality just a little too far and end up shooting yourself in the ass. A lot of cover bands in my area wonder why they aren't getting the gigs if they are playing the same songs as the popular bands. Usually, they are so far out of the ball park, compared to other bands, they sound like a bad parody. It's a fine line, and you have to know how to stay on the right side of it. You can get away with some things, but take too many liberties and people won't appreciate it so much.
A lot of bands I see say they are playing it "their way," but in truth, they lack the necessary skills to learn the basic progressions and melodies. Audiences aren't as detail-oriented as musicians, but they know the difference between a clever and acceptable re-working of their favorite song and a hack job.