I think that a good cover should somehow capture the best parts of both the person/group covering it and the original. A good cover shouldn't sound exactly like the original, but it also shouldn't venture so far away that it bastardizes the original message either. Let's use Jeff Buckley's version of "Hallelujah" as an example of a great cover. His voice alone is enough to make his version magical, but the instrumentation is also wildly different. Buckley's electric guitar is a far cry from Cohen's original synths, drums, and choir.
Another cover that I would call one of the ballsier I've heard is Cush's version of Prince's "I Would Die 4 U". It takes Prince's classic Minneapolis Industrial Dance sound and turns it on its head by stripping it down to an Oh Brother, Where Art Thou? style spiritual with only an acoustic guitar, country organ, and a dusty voice for most of the song (the solo is banged out on a typewriter). The result is something almost unrecognizable from the original. I had a roommate that was a big Prince fan and not even he recognized it until after many, many listens.
Old Derek Brown posted this version of a Springsteen song today and, although my first reaction was that he was trespassing on sacred ground, I think it's a fine example of how to properly cover a song.