Am I right in thinking that there is not a single Talking Heads in the entire RS 500? That's just inexcusable...

Here is a tally of songs from the top 500, by artist:

23
The Beatles

14
The Rolling Stones

13
Bob Dylan

11
Elvis Presley

8
U2

7
The Beach Boys
Jimi Hendrix

6
Chuck Berry
James Brown
Led Zeppelin
Prince
Sly and the Family Stone

5
Buddy Holly
The Clash
The Drifters
Elton John
Ray Charles
The Who

4
Al Green
Aretha Franklin
Bob Marley and the Wailers
Bruce Springsteen
Jay-Z
Creedence Clearwater Revival
David Bowie
The Everly Brothers
The Four Tops
Little Richard
Marvin Gaye
Muddy Waters
Nirvana
Roy Orbison
Sam Cooke
Stevie Wonder

3
Aerosmith
The Animals
Blondie
Bo Diddley
The Byrds
Elvis Costello
Guns N' Roses
The Isley Brothers
Johnny Cash
Neil Young
Otis Redding
Pink Floyd
Ramones
Simon and Garfunkel
Smokey Robinson and the Miracles
The Supremes
The Temptations
Van Morrison
The Velvet Underground
Wilson Pickett

2
AC/DC
Alice Cooper
The B-52's
The Band
Bee Gees
Ben E. King
Big Star
Bill Withers
Black Sabbath
Cream
Crosby, Stills, Nash (& Young)
The Cure
Dion
Donna Summer
The Doors
Dr. Dre
Eddie Cochran
Fats Domino
Hank Williams
Howlin' Wolf
Jackie Wilson
Janis Joplin/Big Brother and the Holding Company
Jefferson Airplane
Jerry Lee Lewis
Jimmy Cliff
Joni Mitchell
The Kinks
The Lovin' Spoonful
Lynyrd Skynyrd
Martha and the Vandellas
Michael Jackson
Patsy Cline
The Police
Public Enemy
Queen
R.E.M.
Radiohead
The Righteous Brothers
Rod Stewart
The Ronettes
The Sex Pistols
The Shangri-Las
The Shirelles
The Smiths
The Staple Singers

1
? and the Mysterians
50 Cent
Aaron Neville
ABBA
Afrika Bambaataa and the Sonic Soul Force
The Allman Brothers Band
Amy Winehouse
Archie Bell and the Drells
B.B. King
Barrett Strong
Beastie Boys
Beck
Beyonce
Big Joe Turner
Bill Haley and His Comets
Billy Joel
Blue Oyster Cult
Bobbie Gentry
Bobby Darin
The Bobby Fuller Four
Bonnie Raitt
Booker T and the MG's
The Box Tops
Buffalo Springfield
Carl Perkins
The Carpenters
The Chantels
Cheap Trick
Chic
Chubby Checker
The Coasters
Coldplay
The Crystals
Daft Punk
Deep Purple
Del Shannon
The Dells
The Dell-Vikings
Depeche Mode
Derek and the Dominos
Dido
Dionne Warwick
The Dixie Cups
Dolly Parton
Don Henley
Dusty Springfield
The Eagles
Earth, Wind and Fire
Eric B. and Rakim
Eric Clapton
Eurythmics
Fleetwood Mac
The Five Satins
The Five Stairsteps
The Flamingos
Foreigner
Frankie Lymon and the Teenagers
Franz Ferdinand
Gene Vincent and His Blue Caps
George Harrison
George Jones
Gladys Knight and the Pips
Glen Campbell
Gloria Gaynor
Gnarls Barkley
Grandmaster Flash and the Furious Five
Green Day
Iggy Pop
Ike and Tina Turner
The Impressions
The Jackson 5
Jackson Browne
The Jam
James Taylor
Jeff Buckley
Jerry Butler
Joan Jett and the Blackhearts
John Cougar Mellencamp
John Lee Hooker
John Lennon
Joy Division
Justin Timberlake
Kanye West
Kelly Clarkson
The Kingsmen
Labelle
Lavern Baker
The Left Banke
Little Eva
Lou Reed
Love
M.I.A.
Madonna
The Mamas and the Papas
Metallica
MGMT
Missy Elliott
The Modern Lovers
Mott the Hoople
N.W.A.
New York Dolls
Norman Greenbaum
The Notorious B.I.G.
OutKast
Parliament
Patti Smith Group
Paul McCartney
Pavement
The Penguins
Percy Sledge
Pixies
The Platters
Procol Harum
R. Kelly
Randy Newman
Rick James
Rihanna
Ritchie Valens
Roberta Flack
The Ronettes
Run-DMC
Salt 'N Pepa
Sam and Dave
Screamin' Jay Hawkins
Sinead O'Connor
Solomon Burke
Sonny and Cher
The Spencer Davis Group
Steppenwolf
The Stooges
The Strokes
Sugarhill Gang
Television
Them
Tina Turner
Tom Petty
Toots and the Maytals
Tracy Chapman
The Troggs
2Pac
UGK
The Verve
Weezer
The White Stripes
Willie Nelson
Yeah Yeah Yeahs
The Young Rascals
The Zombies

ZERO
ABC
Air
Alanis Morissette
Animal Collective
Antony and the Johnsons
Aphex Twin
Arcade Fire
Arctic Monkeys
Art Blakey
Augustus Pablo
The Avalanches
Basement Jaxx
Belle and Sebastian
Bessie Smith
Bill Evans
Bill Monroe
Billie Holiday
Billy Bragg
Bing Crosby
Blur
Bjork
Boards of Canada
Bob Seger
Bon Jovi
Bonnie "Prince" Billy
Boogie Down Productions
Boston
The Breeders
Brian Eno
Britney Spears
Bryan Adams
Buzzcocks
Can
Captain Beefheart and His Magic Band
Carole King
The Carter Family
Cat Power
Charles Mingus
Charlie Parker
The Chemical Brothers
Count Basie
Crowded House
Curtis Mayfield
Cyndi Lauper
Cypress Hill
D'Angelo
Dave Brubeck
De La Soul
Dead Kennedys
Deee-Lite
Def Leppard
Devo
Dexys Midnight Runners
Dinosaur Jr.
Dire Straits
Dizzee Rascal
Dizzy Gillespie
DJ Shadow
Duke Ellington
Echo and the Bunnymen
Ella Fitzgerald
Elliott Smith
Emmylou Harris
Eric Dolphy
Erykah Badu
Faith No More
Fairport Convention
The Fall
Fatboy Slim
The Flaming Lips
Fleet Foxes
The Flying Burrito Brothers
Foo Fighters
Frank Sinatra
Frank Zappa/The Mothers of Invention
Frankie Goes to Hollywood
Fugazi
Fugees
Gang of Four
Garbage
Gene Autry
Genesis
George Michael
Glen Miller
The Go-Betweeners
Gorillaz
Graham Parker
Gram Parsons
Grateful Dead
Happy Mondays
Harry Nilsson
Herbie Hancock
Hole
Hot Chip
The Human League
Husker Du
Ian Dury
Ice Cube
Interpol
Iron Maiden
Isaac Hayes
Jane's Addiction
Janet Jackson
Jeff Beck
The Jesus and Mary Chain
Jethro Tull
Jimmie Rodgers
Joao Gilberto
Joe Cocker
John Cale
John Coltrane
Judy Garland
Justice
Kate Bush
Kelis
The Killers
King Crimson
Kiss
The Knife
Kraftwerk
Lauryn Hill
The La's
LCD Soundsystem
Leadbelly
Leonard Cohen
The Libertines
Little Feat
Liz Phair
LL Cool J
Loretta Lynn
Louis Armstrong
Lucinda Williams
Madness
Magazine
Manic Street Preachers
Massive Attack
Max Roach
MC5
Mercury Rev
Miles Davis
Moby
Modest Mouse
The Monkees
Morrissey
Motorhead
My Bloody Valentine
Nick Cave
Nick Drake
Nico
Nine Inch Nails
The O'Jays
Oasis
The Orb
Orbital
Ornette Coleman
Paul Simon
Pearl Jam
Pere Ubu
Pet Shop Boys
Peter Gabriel
PJ Harvey
The Pogues
Portishead
Prefab Sproud
Pretenders
Primal Scream
The Prodigy
Public Image Ltd.
Pulp
Queens of the Stone Age
Rage Against the Machine
The Rapture
Red Hot Chili Peppers
The Replacements
Richard and Linda Thompson
Robert Johnson
Robert Wyatt
The Roots
Roxy Music
Rufus Wainwright
Rush
Ry Cooder
Ryan Adams
Santana
Scott Walker
Serge Gainsbourg
The Shins
Sigur Ros
Slayer
Sleater-Kinney
Small Faces
Smashing Pumpkins
Snoop Dogg
Soft Cell
The Soft Machine
Sonic Youth
Sonny Rollins
Soul II Soul
Soundgarden
The Specials
Spiritualized
Spoon
Stan Getz
Steely Dan
The Streets
The Stone Roses
Suede
Sufjan Stevens
Suicide
Super Furry Animals
Supergrass
System of a Down
T. Rex
Talk Talk
Talking Heads
Teenage Fanclub
Thelonious Monk
Thin Lizzy
Tim Buckley
TLC
Todd Rundgren
Tom Waits
Tori Amos
Tortoise
Traffic
A Tribe Called Quest
Tricky
TV on the Radio
The Undertones
Underworld
Van Halen
Violent Femmes
Warren Zevon
Wayne Shorter
Wilco
Wire
Woody Guthrie
Wu-Tang Clan
X
XTC
Yes
Yo La Tengo
ZZ Top

...and many more...feel free to add to the list

I can't believe Free Man In Paris got knocked off for some of those newer pop and rap songs. (Instead of some of the newer songs that actually deserved it)

Rolling Stone's lists have a history of being economically influenced, of course.

Thanks Daniel. It would be interesting to see which of the artists with zero songs in the RS top 500 are viewed as the best by the AMers.

Well subjectively I'd probably go with a different bunch of acts but objectively looking at legacies, influence and acclaim I feel that these are probably 25 of the most surprising omissions:

Arcade Fire
Buzzcocks
Curtis Mayfield
De La Soul
Devo
Frank Sinatra
Frank Zappa/The Mothers of Invention
The Jesus and Mary Chain
Louis Armstrong
Oasis
Paul Simon
Pearl Jam
Pet Shop Boys
Pulp
Rage Against the Machine
Red Hot Chili Peppers
Roxy Music
Serge Gainsbourg
Sonic Youth
The Specials
The Stone Roses
T. Rex
Talking Heads
Tom Waits
Woody Guthrie

and yet MOMENT OF SURRENDER.

I was very surprised to see Woody, T Rex or Devo as what you consider the obvious choices ; so here are the artists in 2008 artists poll top 100 which do not have a single song in the RS500 :

100. LCD Soundsystem
99. Wu-Tang Clan
98. Pearl Jam
97. Portishead
95. Frank Sinatra
90. Cocteau Twins
87. Kraftwerk
82. Neutral Milk Hotel
80. Pulp
79. Guided by Voices
73. Super Furry Animals
71. Nick Cave
68. Sufjan Stevens
62. Frank Zappa
61. Hüsker Dü
59. John Coltrane
58. The Replacements
53. Leonard Cohen
49. The Flaming Lips
48. Scott Walker
45. Massive Attack
43. Oasis
40. PJ Harvey
38. Steely Dan
37. The Smashing Pumpkins
36. Elliott Smith
35. Wilco
33. Arcade Fire
31. Belle and Sebastian
30. Björk
28. Nick Drake
27. Miles Davis
25. Tom Waits
24. Blur
21. Talking Heads

Some of those names are not really surprising since it is a RS list, but no Oasis still seems strange to me coming from them!

Okay so T Rex in my eyes would be nailed on for a Rolling Stones list. They have a handful of real 70s anthems, pioneered glam rock etc. I suppose Guthrie's influence stretches beyond his output so that's fair. As for Devo I would've assumed at least Whip It or Mongoloid could've cracked the lower echelons, but on second thought maybe not as RS slated them for their Satisfaction cover back in the day

Can't say that I miss either Devo or T Rex, despite seeing T Rex in my first concert back in 1970-1971 when they played before Three Dog Night at the Nassau Colosseum. I realize that Glam Rock had its day and that T Rex may have been one of the early practitioners, but were they really "pioneers?"

Gutherie's music doesn't do much for me either, but at least his influence seems more enduring and credible.

Gimme Shelter should be higher, in my opinion. It's at 38 now. "I Want to Hold Your Hand," should be much lower, I think. It has historical interest, but who rocks out to that song, especially in view of the much better and richer Beatles songs that came after? Help!, for example, has aged much better than I Wanna Hold Your Hand. What are we, 12 years old? We shtoink on the 4th date. Also Gimme Shelter is one of Obama's favorite Stones song, and the Stones are one of his top 3 bands. "Gimme Shelter is so powerful it's like a nonstop weather system that should be tracked by the International Hurricane Agency"
My Generation is also overrated. It has the famous line "I hope I die before I get old," of course, but who really gets into the off-rhythm stuttering. I think My Generation seems like a gawky imbecile child compared to Wont Get Fooled Again.

Voodoo Child is the most exciting guitar song I've ever heard, it has a primal energy that makes even the best of Clapton sound tame. It's not in the top 100. It should be in the top 20. It's like a volcano of inspiration in a tea room full of murmuring mediocrities. It makes ACDC and Tom Petty and David Bowie's rock experiments sound wafer-thin and square by comparison. I like Layla, but the famous riff of Layla sounds hurried and unfunky to me compared to the riffs cascading through Voodoo Child.