I’m going to third the suggestion of Johnny Cash’s Hurt cover. I think it’s far superior to the original Nine Inch Nail’s version.
Agreed, it’s not only the melody but who it is singing it. You just know Johnny Cash has seen more pain than Trent Reznor can dream of.
‘I wear this crown of thorns’…though…really Cash? That’s not the line.
Beck’s cover of Bowie’s Diamond Dogs. (Here for another Bowie live version.) I think Beck’s cover is much truer in feel to the surrealistic source material (Samuel Delany’s Dhalgren) And it gets rid of the moronic genocide line from Bowie’s most played performance.
I love the Over The Rainbow part of that song. Then he segues into What A Wonderful World, though, and the whole thing is ruined. 
Bishop Allen did a cover of Eve of Destruction that I like quite a bit. Granted, I wasn’t really familiar with the original when I heard the cover.
Somewhere or other Reznor himself acknowledges that Cash’s version is better. Can’t find the cite, sorry…
Disturbed’sDown With The Sickness is a really effective, raw song.
Richard Cheese’s cover, however, is spot-on perfect as the background music for the montage of mall life in the Dawn of the Dead remake.
Hank Williams is a legend and all, but I much prefer Fats Domino’s Jambalaya to his.
I was going to bring this up except that I don’t think it’s a radical re-interpretation, just an ass-kicking one.
The video cranks it to the next level, and his death not long after makes it one of the most perfect and moving elegies ever.
Goldfrapp’s interpretation of Yes Sir I Can Boogie.
They turn a cheesy seventies disco tune into a sexy, filthy and mature song
Also their interpretation of Let’s Get Physical is also sleazy and better for it http://www.youtube.com/watch?v=3w4EnuPMK9Q
The Carolina Chocolate Drops’ cover of Hit 'em Up Style is a tad bit different from Blu Cantrell’s recording…
Johnny Cash’s cover of Rusty Cage by Soundgarden is pretty kick ass as well
I really love the choral version of “I saw the Sign” in the film Slackers, originally by Ace of Base.
That is a good one. I also love:
And of course Ben Fold’s cover of “Bitches ain’t shit” originally by Dr Dre.
I’m kind of fond of a ukele version of Paparazzi,but I’mhaving trouble finding it.
My favorite rendition of this album is the version with Indigo Girls and Big Fish Ensemble. In addition to having the lesbian duo play Mary and Jesus, it’s the only version I’ve heard that really tries to rock it and make it sound great, whereas most other version are talk-singy or have mediocre singers.
I kind of like his “Personal Jesus” cover too…
Probably because it was actually Poker Face LOL.
Daughtry’s Poker Face is also a good soulful crooning reinterpretation.
Seem’s like there are a ton of excellent reinterpretations of Take On Me. I particularly like Annie B Sweet’s and ukebuckets’.
Machinae Supremacy’s cover of Gimme More.
Tom Waits does a downright creepy version of Heigh Ho (The Dwarfs Marching Song)
Hold on now, can you really say that? The original is a work of pure genius and that kind of thing doesn’t emerge from a vacuum.
The Cash cover with the video is runaway epic, though. The two versions are different enough that I can’t say one is vastly superior to the other.
Breakin’ Up is Hard to Do (Neil Sedaka 1962)
Breakin’ Up Is Hard to Do (Neil Sedaka 1975)
Sedaka successfully reinterprets his up-tempo pop hit as a slow ballad.
And this cover of Iron Maiden’s Number of the Beast, by Australian band Powderfinger, is one of my favourites 
I’ve posted this before, but I still love Bowling For Soup’s take on Fergie’s “London Bridge”:
The Flying Lizards deserve a mention for reinventing Money (That’s What I Want) into near unrecognizability. They also do a cover of James Brown’s Sex Machine that is so deadpan it’s hilarious.
In the same vein:
How about the same song by Max Raabe (here presented over Britney’s original video)? Raabe is a wonder - see also Sexbomb.
Dr. John’s almost dirgelike rendition of “When the Saints Go Marching In.”