Blender.com has an awesome list of songs that you probably didn’t know were covers. Examples? “Bette Davis Eyes”, “Istanbul (Not Constantinople)” and “Barbara Ann”.
An interesting tidbit: a lot of folks from “my” generation know the song “Always On My Mind” from the Pet Shop Boys’ cover of it. Many from my generation (including me) were somehow under the impression that it was originally a Willie Nelson song. Well, Willie covered it too, as did Elvis Presley. Until today, however, I had no idea that Brenda Lee actually sang the song originally. You learn something new every day, I guess!