Devo’s covers of (I Can’t Get No)Satisfaction and Working in a Coal Mine
I Can See Clearly by The Holly Cole Trio
Daniel - by Fuel
Going to California - by Fuel
some Led Zepplin song that I don’t know the name of, it’s like Ramblin’ On or something - by Fuel and Train
Some obscure, some well-known, and some that completely displaced the originals:
Time After Time, Tuck and Patti (jazz duo)
RESPECT, Aretha Franklin
It’s a Thin Line (Between Love and Hate), The Pretenders, Annie Lennox
Say a Little Prayer, Aretha Franklin
Venus, Bananarama
Bizarre Love Triangle, Frente!
Peace Train, Dolly Parton
Fancy, Reba McEntire
And in researching my answer I stumbled across a fascinating website: The Covers Project. Enjoy.
Best Cover Ever.
Worst Cover Ever.
While I’m here let me add that the White Sripes cover of Dylan’s One More Cup of Coffee is pretty damn good.
Kim Wilde: Keep Me Hanging on
Slayer: In-A-Gadda-Da-Vida From the “Less Than Zero” Sound track.
Orgy: Blue Monday
UB40: Red Red Wine
Beach Boys: California Dreaming
Stryper: Shining Star
The late great Townes Van Zandt.
Nancy Griffith did a nifty version of Tecumseh Valley on Other Voices, Other Rooms.
I’ll second a few:
“All Along the Watchtower” - Jimi Hendrix
“Because the Night” - 10,000 Maniacs
“Sweet Jane” - Cowboy Junkies
“A Little Help From My Friends” - Joe Cocker
“Hallelujah” - Jeff Buckley
…and add a few:
“Take On Me” - Reel Big Fish
“Smooth Criminal” - Alien Ant Farm
“When Doves Cry” - Ani DiFranco
“Maggie May” - Melissa Etheridge
“Man in the Long Black Coat” - Joan Osborne
…along with a group of Depeche Mode covers…
“Somebody” - Veruca Salt
“Master and Servant” - Locust
“Shake the Disease” - Hooverphonic
“I Feel You” - Apollo Four Forty
“Policy of Truth” - Dishwalla
“Everything Counts” - Meat Beat Manifesto
I’d also include Rammstein’s version of DM’s “Stripped”, but only for the unintended humor. I like Rammstein, but this wasn’t the song for them.
Misty - Ray Stevens, never could stand the Johnny Mathis version.
On some secluded avenue - Spike Jones and his city slickers 
(this was definately an improvement on the mawkish original.
I cannot agree about Bananarama’s version of “Venus” being any good at all, it was just a cynical excercise in keeping in the public eye and it was terrible when compared to the original.
Money - Beatles, not better than the oroginal but good all the same.
Money - Flying Lizards, strange version but pretty good.
Fire and rain - Tim Hardin, sadly he didn’t live too much longer which made this almost self prophetic song all the more poignant.
Without you - Originally by Badfinger but the version by Nielson is much better known.
Under the boardwalk - Tom tom club, still not as good as the Drifters but not at all bad.
Poison Ivy - The Lambrettas, reasonable version of the Coasters number
Wherever I lay my hat - Paul Young, originally on a Marvin Gaye B-side, it has a completely differant treatment to the original and is just as good.
Ian Tyson does a rather good cover of “Over the Rainbow”. Very mournful.
Metallica’s ass-kicking cover of “Whiskey in the Jar”, however, is the opposite of “mournful”, but still belongs on this list.
I’ll second GNR’s covers of “Knockin’ on Heaven’s Door” and “Live and Let Die”, but their “Sympathy for the Devil” is a pale shadow of the Stones’ version.
No! Morten Harket is crying…
Oh, I almost forgot Belinda Carlisle’s version of “I Feel Free”.
The Ramones generally did good covers. I like “Out of time” and “Needles and pins.” The later required an unusual singing style for Joey.
On the other hand, there’s a Latino Ramones tribute group “The Ramondos” or some such and their cover of the Ramones’ cover of “Needle and Pins” is not so good.
Social Distortion doing Johnny Cash’s Ring of Fire
Six Feet Under covering Iron Maiden’s Wrathchild and Thin Lizzy’s Jailbreak
Tiamat covering The Rolling Stones Sympathy for the Devil
NP: The Clash - London Calling