Landslide by:
Hose Feliciano’s version of “Light My Fire” is quite different from the Doors’ original recording.
The Vitamin String Quartet has done chamber music versions of many acts, including The Clash and The White Stripes. It seems like a bit of a schtick, though – not really what the OP had in mind, I think.
Gin and Juice, originally done by Snoop Dogg, was covered by Phish in a wonderful version.
That’s The Gourds, not Phish.
“Wherever I Lay My Hat (That’s My Home)” by Marvin Gaye started life as a jaunty, yet matter of fact tale sung by a self confessed lothario to one of his conquests who thinks he is something more. Paul Young’s cover adds a sense of melancholy to the song which adds up to a sense of ambiguity about what the man thinks about his actions. I love both versions of the song.
Dexy’s Midnight Runners covered Status Quo’s excellent “Marguerita Time” as a waltz.
Tori Amos obviously has a pixieish sense of humour in her choice of cover versions. Her covers of “That’s What I Like” & “London Girl” by Chas & Dave are charming and delightfully unlikely.
I don’t think anyone here has mentioned Chris Cornell’s reimagining of Michael Jackson’s song “Billie Jean”. [ David Cook pretty much won American Idol on the strength of this version - and his vocal ability, of course ]
“Hey Ya” by Outkast http://www.youtube.com/watch?v=XvIw5ZqC1ms and
“Hey Ya” by Mat Weddell http://www.youtube.com/watch?v=8-8nkkOA_AM
Black Sabbath Blue suede shoes.http://www.youtube.com/watch?v=_uryWJ1T1q4
Made ya look!
Johnathan Coulton- Baby got back-http://odeo.com/episodes/1519801
“John the Revelator” is a song done too many times to keep track of, This version by Gov’t Mule is my favorite-http://www.youtube.com/watch?v=jMSRP3kpVMs
Lucy in the Sky with Diamonds - The Beatles
Lucy in the Sky with Diamonds - William Shatner
Best Khan Noonien Singh voice- “SHATNER”!!!
I would like to present to you one ANTI-THANK YOU for that. 
That video is SO DAMN peppy… Thank you for that Village People cover…
*
I ain’t got… No-Body (No Body!)!*
I know the video that is often mistakenly attributed to Phish is actually the Gourds, but Phish did do a cover of “Gin and Juice”. It’s on their Hampton Comes Alive CD set.
My favorite “version” of this song.
Just couldn’t resist.
Johnny Cash did a cover of NIN’s “Hurt” about a year before he died. It’s a teensy smidge different from the original.