I like the folk version of The Rolling Stones’ “Start Me Up” as performed by The Folksmen from the soundtrack to “A Mighty Wind”. I always get a chuckle from listening to it!
The version of Close to You from the film Mirrormask.
I kinda like this Finnish cover band called Leningrad Cowboys. Here’s a clip of them rocking Sweet Home Alabama with a Russian army choir:
It’s obvious they do not get a lot of the references in the lyrics, but that’s ok, somehow.
Just nobody tell Bill Watts I like these guys. He already thinks I’m a liberal.
Wuthering Heights as performed by The Ukulele Orchestra of Great Britain.
Devo, “Are You Experienced”
“Baby Got Back”, Gilbert and Sullivan style.
Their cover of These Boots Are Made For Walking is truly bizarre, but spectacular. Balalaikas!
I could listen to this over and over. Thank you for introducing me to the Afghan Whigs. I wasn’t familiar with the group other than the name.
The Cardigans’ version of Black Sabbath’s “Iron Man” – in this slow dreamy version, the big metal guy comes across as woefully misunderstood rather than angry and vengeful (makes me think of the cover of the Queen album News of the World)
Speaking of the Cardigans, they do a duet with Tom Jones of “Burning Down the House” that is better than the Talking Heads version, if that is possible. This is not a major reconstruction of the original though – the others on my list here are virtually unrecognizable without a lyric sheet.
Andy Prieboy of Wall of Voodoo released an EP called “Montezuma Was a Man of Faith” which contains a hillbilly blues version of Led Zeppelin’s “Whole Lotta Love” (apparently featuring an uncredited Johnette Napolitano of Concrete Blonde). Altho I love the Zep version a whole lotta, Prieboy totally takes the piss out of it. It’s wonderful.
Another great LZ reconstruction is A Perfect Circle’s version of “When the Levee Breaks” on the eMOTIVe album. eMOTIVe is entirely made up of reconstructed covers but most of them range from dumb to horrifyingly bad. This one works.
The “Two Rooms” album of major artists re-recording songs by Elton John and Bernie Taupin. It’s a good album as The Who, Tina Turner, Eric Clapton, Phil Collins and many others redo EJ-BT songs in ways that make you think the songs were written for them. But only a couple of artists actually re-think the songs and give them an entirely new spin. The best of these is Kate Bush doing “Rocket Man.”
I’ve got my fair share of covers—some of them mentioned here—but the one that comes to mind is We’ve Got All the Time in the World, by the Puppini Sisters. Somewhere between the Andrews Sisters and Parisian street music.
After that, I’d say Kashmir as performed by the London Philharmonic…but from what I understand, this is what the song always sounded like to Zeppelin fans. 
I LOVE this. And I’m not really into orchestral music. And the Afghan Wigs-- that should be Dick Cheney’s theme song.
You’ve probably seen this but I still love Mat Weddle’s acoustic Hey Ya
I adore David Cook’s version of Billy Jean (it’s based off a cover by Chris Cornell, but it’s better than that one.)
Rolf Harris’ cover of Stairway To Heaven was great partly because of the outrage it provoked in those people who take the Led Zep original far too seriously, and partly because in response to that outrage, Rolf pleaded complete innocence, claiming he’d only seen it as sheet music and never actually heard the original, incensing them even further.
Lately I can’t stop listening to Evelyn Evelyn’s “Love Will Tear Us Apart”. They’ve turned it into this halting, fragile, beautiful little thing with just a ukulele and a bit of piano.
(Speaking of Amanda Palmer and the ukulele, she also does a minimalist “Creep” that’s frankly kind of silly but also has something very right about it.)
Janis Joplin, with Big Brother and the Holding Company’s version of Gershwin’s Summertime. Not so much for Janis’s vocal (though she was a genius, and everything), but for the amazingly raunchy guitar. (This YouTube version does not quite live up the one on the original album, I fear, but you get the idea.)
Ace of Spades as covered by Hayseed Dixie. Right up there with the Motorhead version and leagues better than Metallica’s.
They do a number of covers of metal songs, but this one is my favorite
