I've gotten into my head that I want to build a deck based around the idea of stories and songs. I made a Lore/Leadership deck that goes along those lines, but it was a little weak and I've since gotten a copy of the Hobbit saga expansion with the "Very Good Tale" card.

Cards I definitely want to include:

A Very Good Tale

Campfire Tale

Lover of Songs

Some Songs! (With Rivendell Minstrel of course)

Any ideas?

Cool idea. Bilbo and Elrond would make a good heroes thematically, and having Elrond allows you to put some allies of varied sphere in there. The LotR LCG Databse at http://lotrlcg.com/ can help you locate thematic cards (search "song" or "tale"), but it's not 100% up to date.

Songs and tales span all of the spheres. Song of Mocking - tactics. Song of Earendil - spirits. Durin's Song (event) - leadership. Love of Tales - lore. Including a Dwarf hero and Navri's Belt could help you deal with this, and you could then use a Legacy of Durin, which you could think of as a bit of lore about the dwarves (so it fits thematically). But if you're including song cards anyway, the songs of wisdom/travel/kings/battle could do the work of Navri's Belt. Problem here is including a ton of cards that don't help deal with enemies or locations. To compensate, you'll need lots of card draw!

Gleowine (Lore) is also a minstrel and would fit thematically. I mentioned Legacy of Durin already, and if you've got Bilbo as a hero you'll be getting some draw from him as well. You also already mentioned Campfire Tales.

The new Master of Lore (Lore) in Heirs of Numenor fit thematically.

If you can get a copy of Love of Tales on a couple of your heroes early on, you stand to make some money when you play those songs, too. Born Aloft will work well with Rivendell Minstrel to seek out specific songs. Master of Lore can help to offset the cost of the minstrel.

Having said all that, we don't really have any combat-ready allies in your deck. Not sure how to work fighters in to your theme here, so I'll leave that to someone else! Good luck!

I'm not thinking that it will be effective as a solo deck, but as sort of a support deck.

Gildor's Counsel and Elrond's Counsel I think would also fit the theme.

Right now I'm thinking of running Bilbo, Elrond, and Berevor as my heroes.