Ah! I posted the Folk Hey Ya in the wrong thread and now you’ve beaten me to the punch.
I like Max Raabe und sein Palast Orchester’s cover of Let’s Talk about Sex. The Droyds’ Girls on Film is good, too. And while we’re on COIL (squee, Critical1) their version of Leon Cohen’s Who by Fire is pretty sweet.
Tanya Tucker’s cover of Someday My Prince Will Come is a lot of fun.
Sarah Brightman’s Whiter Shade of Pale
My favorite Britney Spears covers are Toxic by Stevie Ann, Ahmet and Dweezil Zappa’s cover of Hit Me Baby One More Time, and you haven’t really lived until you hear Max Raabe’s version of Oops I Did it Again.
Dynamite Hack’s “Boyz in Da Hood” – http://www.youtube.com/watch?v=tVkMU1iRNYE
Cake’s “War Pigs” (Ignore the video–they apparently had a contest for it) – http://www.youtube.com/watch?v=xyJMufGx7fo
And with another Gnarls Barkley cover, here’s Ray Lamontagne doing “Crazy” – http://www.youtube.com/watch?v=6mEfDSP4g_U
Can’t believe I forgot Alanis Morissette doing “My Humps” – http://www.youtube.com/watch?v=W91sqAs-_-g
And I also forgot Chris Cornell doing “Billie Jean” – http://www.youtube.com/watch?v=uIvbjmQadSM
Thank you thank you thank you. I think I’ve just found my new favourite song. 
Speaking of cool folk covers of peppy songs, the Iron and Wine cover of Such Great Heights is another one of my favourites. (Ben Folds does a really fun version, but it’s just a bit too close to the original to be truly genius)
Cassandra WIlson. I can’t pick just one. Here’s Robert Johnson’s .32-20 Blues.
I always enjoyed Rolf Harris’s version of Stairway
One of my favorites is the Tubes live cover of “Love Will Keep Us Together” (the huge Captain & Tennille hit from the 1970s).
The link is only to a Tubes discography page–I wasn’t able to find a video or audio clip available online.
The Gourds cover of Gin and Juice (video contains some NSFW language)
Thirding the Hey Ya cover.
Still, my favourite folk cover ever remains Nina Gordon’s Straight Outta Compton. NSFW lyrics, for the benefit of anyone (all five of you) who doesn’t know the song.
ETA: Oh, yeah. I share the love for Iron & Wine’s Such Great Heights.
If an artist can “cover” his own song, I nominate this version of **Further on Up the Road **by Bruce Springsteen.
The Happy Schnapps Combo did a lovely polka rendition of “Born to be wild.”
It wakes me right up in the morning!
I prefer David Cook doing Chris Cornell doing “Billie Jean” – http://www.youtube.com/watch?v=BUfbLtZHrog (ignore the video)
Ghost Riders in the Sky as sung by The All-American Boys Chorus, Die Apocalyptische Reiter, The Baja Marimba Band, The Bar G Wranglers, BCB Band, The Be Arthurs, Chris Fender Black & Black Cat, Don Bletz, The Blues Brothers, California Guitar Trio, Johnny Cash, The Chipmunks, Susan Christie, Scatman Crothers, Children of Bodom, Dick Dale, Deadbolt, Duane Eddy, Phil Emmanuel, Firewater Creek, Kent “Toast” French (The World’s Fastest Clapper), Andy Garrett, Goin’ South, Rene Guylline, Wade Hawthorne, Burl Ives, Jet Screamer, Spike Jones, Judge Trev, Don Kelley Band, Frankie Laine, Neil Levang (of the Lawrence Welk Show Band), Cristo Lewis (7 years old), Me First and the Gimme Gimmes, Vaughn Monroe, Ninth House, Oh Boy, The Outlaws, Elvis Presley, The Ramrods, R.E.M., Riders in the Sky, Marty Robbins, The Saddle Pals, The Scorpions, Sha Na Na, The Shadows, J.D. Simo, Spiderbait, Ned Sublette, Toy Dolls, Trunk, The Tubes, Valyaev and Volkov, The Ventures, Wild Range Grrls
“Dreams” by the Allman Bros is a GREAT tune
and is quite different, but ALSO great when covered by Molly Hatchet.
I love both of these songs to death, and am endlessly fascinated that one morphed into the other. The same, but different.
The second vid is not a live performance, but it has a nice slideshow of fantasy art and space pics.
I suppose that Molly Hatchet isn’t terribly unconventional, but I thought they were sufficiently different enough from the original to qualify.
Shawn Colvin did a great cover of Gnarls Barkley’s “Crazy” as well.
I like Elbow’s version of Independent Woman, particularly when performed by the North English kittens.
Well I like it better than Destiny’s Child’s version, anyway.
I can’t pick just one.
Scissor Sisters- Comfortably Numb Warning: if you’re anybody but me, you’ll hate this one.
If by non-traditional, you mean covers that reinterpret the song, I’ve always enjoyed this one.
Cocteau Twins- Strange Fruit (Anecdote- this was the first version of the song that I heard and between Liz Fraser’s odd pronunciation when she sings and her tendency to sing meaningless but pretty mouth music, I hadn’t paid attention to the lyrics. But then I noticed she was singing something that went “sudden smell of mumble mumble”. So I sought out the lyrics…:eek::smack::()
Another vote for Devo’s version of “Satisfaction.”
I like the way Wing sings “Dancing Queen” and “My Favorite Things.”
How about Moog Cookbook’s very tongue-in-cheek instrumental version? Totally nerdy, but brilliant, in my opinion. These guys can do no wrong.