Most folks in the U.S. aren't familiar with that brand and symbol, so it would be helpful to describe it further and what you mean by "tell a story".

In general you want a symbol that relates to the product in some way, but an unrelated symbol can be made to work if people associate it strongly enough with the product, or if advertising draws a connection.

For example the MGM movie studio lion originally had little connection with moviemaking (a lion was the mascot of the designer's college), but through association it became a well-recognized symbol.

The logo is an illustration of a dead lion filled with bees, based on the biblical story of Samson:
http://britishfoodhistory.wordpress.com/2012/02/01/golden_syrup/

So looking for similar brands where their logo has a story to tell, not necessarily directly about the brand itself, but the principles behind the brand.

Nipper.
Francis Barraud inherited a friend’s dog when he died, and also his gramophone with a recording of his voice.
The dog would listen to his dead master’s voice through the horn, intrigued.
Barraud painted this scene, and subsequently sold it to the Berliner gramophone company (perhaps inspired by Pears’ use of Millais’ “Bubbles”).
This image of Nipper became the trademark of the Victor Company (the successor of Berliner), and then RCA (the successor of Victor).
Obviously, it symbolizes veracity of sound reproduction—as well as the attraction of listening to the product.

A long time ago my grandfather owned a radio shop and RCA gave him a statue of Nipper to display in his store. It was a popular symbol back then. I've still got it somewhere.

In Britain it's known as HMV, short for 'His Master's Voice'.

Link to a good quality image of the original painting http://en.wikipedia.org/wiki/File:His_Master%27s_Voice.jpg
The trademark dog and trumpet logo US Patent Office registered trademark no. 34,690 of July 10, 1900

Maybe do a google image search for cigar box art?
I'm sure there awesome stories there:
https://www.google.com/search?q=cigar+box+art&rlz=1RMBKJA_enUS573US573&h...

I like the story behind the BMW logo - That is a reference to their history as an early manufacturer of aircraft engines - But it is just a myth.