Pet Shop Boys’ remake of Always On My Mind. Just a little faster than the original. 
Circle Jerks’ Jerks on 45 plays tons of 70s soft rock staples at faster tempos.
Also, how about the Dead Kennedy’s take on Viva Las Vegas?
Emerson Lake and Palmer’s “Hoedown”, originally written by Aaron Copland and performed by an orchestra, is very slightly faster than the orchestra recording I had (and that was on the class syllabus) when doing a paper comparing the two. And my instructor was very intrigued that I actually counted and timed the number of measures needed to determine that fact, because it hardly sounds faster.
Gotta go with Husker Du’s cover of “Eight Miles High”.
You could always try punk/ska covers. Me First and the Gimme Gimmes have done quite a few of those, and they’re pretty good IMNSHO.
A couple examples
Sex Pistols. God Save the Queen.
Not a cover.
Big Black’s cover of Kraftwerk’s The Model.
Forgot to add : there are also punk covers of punk songs :). For example : Rancid’s cover of NOFX’s The 'Brews is much faster than the original. And works much better, IMO.
There’s a couple Spanish language covers of Sweet Home Alabama; the one by Siniestro is considered a classic in its own right (the other Spanish covers I know are covers of this cover). The live version is livelier than the studio one I linked, but I can’t find a live version that sounds decent in Youtube.
The Georgia Satellites’ version of the Beatles’ “Don’t Pass Me By” is a lot faster than the original.
The Rolling Stones’ “Not Fade Away” is a lot faster than Buddy Holly’s.
Jim Capaldi released an uptempo version of “Love Hurts” at the same time as Nazareth, which was so different that it was a long time before I noticed it was the same song. I loved his version but disliked Nazareth’s, which is no doubt why Nazareth had a top-10 smash in the U.S., while the Jim Capaldi version peaked at #97.
Paul Anka’s Rock Swings album turns a bunch of classic rock songs into lively jazz pieces. Pretty awesome.
How do you speed up “It’s the End of the World as We Know It (and I Feel Fine)”?
I came in here to post about them. My favorite is Rainbow Connection (originally by Kermit the Frog)
Speaking of which, if their version of “Sheena is a punk rocker” puts you to sleep, you’ve got to see a doctor about that narcolepsia.
The Muse version of House of the Rising Sun is a lot faster then folk song version. In addition the music isn’t folksongish at all. Modern instruments are used with a more trance like style,and it’s been redone to included militaristic marching beats, beats that sound like machine gun fire, and somehow they got a guitar to sound planes dogfighting. It ends with the metallic grounded out sound one is said to hear if they called someone just as their location was nuked.
Also if you want something really different try the Rammstein version of Barbie Girl.
The Red Hot Chili Peppers’ cover of Fire. Hendrix’s version is 2:47, the version on the Peppers’ Abbey Road E.P. is 2:03.
Check out Def Leppard’s Yeah! album.
The songs are either going to be the same tempo or faster.
Here’s one of my favorites from the album:
and another one:
Odds are most of the songs are on YouTube.
Here’s the track listing: