I second Captainsolo's suggestion of The Who's rock operas. While Quadrophenia tells a story, it's pretty hard to follow, whereas "A Quick One, While He's Away" and Tommy are a bit more straightforward.

I'll also throw in two moe. songs, "Mexico" (from the album Headseed) and "Kyle's Song" (from Wormwood).

"Mexico" tells the (mostly true, partly embellished) story of one of the band members getting arrested while in Mexico, and "Kyle's Song" tells the story of a friend of the band getting hit by a car after one of their gigs.

Also, Fleet Foxes' "He Doesn't Know Why" (from their self-titled LP), which tells the story of one of the band members' brothers, who descended into drugs and hasn't been heard from since.

Finally, Grandaddy's "Jed the Humanoid" (from The Sophtware Slump), which tells the story of an android falling into a deep depression and drinking itself to death due to its makers forgetting it when newer technologies render it obsolete.

That's all I can think of at the moment, from three of my current-favorite bands.

moe.
"Mexico"
Can't find a studio or non-crappy live version of "Kyle's Song" on Youtube.

Fleet Foxes
"He Doesn't Know Why"

Grandaddy
"Jed the Humanoid"