APC's cover/mesh-up of Love Song by The Cure and Diary of a Madman by Ozzy Osbourne is one of the most clever covers I've ever heard.

link

Also, It took me a while to get into it, but I do like Sarah Blasko's cover of Flame Trees by Cold Chisel. It's probably not as good as the original, but it's different, and beautiful for different reasons.