Damn, I can’t believe I didn’t remember that one! Of course, there is always the king of all Nixon tunes Elvis is Everywhere.
In fact, isn’t Black Velvet by Alannah Myles also about Elvis?
David Bowie by Phish
Elvis is Dead by Living Colour
The Saw Doctors have a song called “I Want To Kiss the Bangles.”
Mojo Nixon had a bunch of others that haven’t been mentioned - he seems to thrive on celebrity references. Just off the top of my head: “Don Henley Must Die”, “We Must Dig Up Howling Wolf”, “Drunk Divorced Floozie (The Ballad Of Diana Spencer)”, and “The Ballad of Country Dick.”
Wayne Gretzky by Goldfinger
Buddy Holly - Weezer. A song about Mary Tyler Moore (or less).
Margaret on the Guillotine - Morrissey. About Margaret Thatcher
Magic Johnson - Red Hot Chili Peppers.
The Last of the Famous International Playboys - Morrissey. About The Krays, criminal twins in England, I believe.
“Song for Myla Goldberg” - The Decemberists
“Mark Rothko Song” - Dar Williams
Would “I Won’t Be Your Yoko Ono” by Dar Williams and “Be My Yoko Ono” by the Barenaked Ladies count?
“Here’s Johnny” - “Weird Al” Yankovic (about Ed McMahon)
“My Baby’s In Love with Eddie Vedder” - Weird Al
“Jerry Springer” - Weird Al (well, it’s about the TV show)
There are probably other Weird Al ones, but I’m blanking.
The 80s Spanish synthpop band Mecano had songs about Salvador Dalí and the Dalai Lama.
Sigfried and Roy and Courtney Love, both by Nerf Herder.
I don’t think so. They’re mentioned in the lyrics–and in Holly’s case, the title–but the song is not “about” them in any legitimate sense (they only serve as similies/metaphors in the lyrics).
All of the following are by U2:
“Until The End Of The World” is Judas singing to Jesus.
“Salome” is about, you guessed it, Salome.
“Elvis Ate America”
“Elvis Presley & America”
“Pride” and “MLK” are both about MLK
Albert Goldman is mentioned in “God Part 2”
“Jesus Christ”
If they do, then “Be My Yoko” by The Bobs has to count, too. (And that can’t be a coincidence, can it?)
Also, “Elwood Decker” by The Bobs
If Peter Gabriel’s “Biko” was mentioned, I missed it.
Also, Elton John’s “Empty Garden” is about John Lennon.
I’ll nominate my favorite:
Dio by The D (aka Tenacious D)
What is it with Vanna and people who want to buy her vowels?
Vanna, Pick Me A Letter by Dr. Dave.
A shorter topic could be about celebrities who have never had a song written about them. And the topic could become even shorter as the list of unsung celebrities becomes known.
Practically every song in Stephen Sondheim’s Assassins qualifies if you include historical figures as celebrities; and even if you don’t, there’s “I Am Unworthy of Your Love,” the ballad to Jodie Foster and Charlie Manson.
There’s a folk song called “Joe Hill” about a union organizer who was charged with murder (possibly framed), convicted, and killed by firing squad in Utah in 1915. He became quite a celebrity during his trial and even Woodrow Wilson tried to intercede on his behalf. I don’t know who wrote the song though.
There’s always Kinky Freidman and the Texas Jewboy’s “Ballad of Charles Whitman”
(Yep, the link has the song).
For those who may not know, Charles Whitman was the person who in 1966 went to the top of the University of Texas Tower (with a huge amount of guns and ammunition) and proceeded to shoot people.
Trivia Note:
(Whitman -but not the song- is also referenced by R Lee Ermey in “Full Metal Jacket”)
Neil Young’s “Keep On Rockin’ In the Free World” is an unflattering “tribute” to George Bush Senior.
“We’ve got a thousand points of light … for a homeless man.
We’ve got a kinder, gentler machine gun hand.”
He should have saved that animosity for “Dubya”. 
I don’t think people who’ve been dead since before the songwriter was born can count as celebrities.
That would be a novel approach to Lyndon Johnson for the time, as the one who saw things as they were (the world spins round; the sun doesn’t really go down).
I would have credited those to Woody Guthrie. He’s the one who put the celebrities in them, after all.
From the New Radicals:
Fashion shoots with Beck and Hanson
Courtney Love and Marilyn Manson
You’re all fakes run to your mansions
Come round here we’ll kick your asses.
“How Do You Sleep,” a poison valentine from John to Paul
“You Made Me Love You” was originally called “Dear Mr. Gable” and sung by Shirley Temple to Clark Gable.
Warren Zevon’s Bill Lee is about a former major-league baseball pitcher famous for such statements as his admission that he used marijuana “as a spice in cooking”. Zevon also wrote Boom Boom Mancini about the boxer of that name.
The subject of Randy Newman’s Kingfish was former Louisiana governor Huey Long.
In 1941, the Les Brown Orchestra (featuring vocalist Betty Bonney) recorded Joltin’ Joe DiMaggio as the “Yankee Clipper” compiled his record 56-game hitting streak. Eventually, the last verse was added after the Cleveland Indians stopped the streak.