First thing that needs to be pointed out, though, is that this is the very first Gimli, from the very first set, so it depicts Gimli as a "standard" Dwarf, meaning, "nothing to do with Elves". It could be said that putting cards in the bottom of the deck is "something in common" he has with Elves, which may have prompted him to not be so prejudicial with them in the first place. Just saying.
Also, giving Dwarves what they already have is not that much fun to "keep the game fresh". I'd actually advise tackling their weaknesses, although without making something quite so overpowered. Since Gimli came from afar to the Council, and he told stories about the dwarven lands and was the ONLY Dwarf available to do so for the Fellowship, I'd reckon his ability to "recount tales" would be considered remarkable - and everything he DID recount would BE a tale. As such, I'd suggest messing with tales, perhaps in a slightly different way, like:
"
conditions with a
token on them are
tales.
Exert Gimli (or Whenever Gimli wins a skirmish - you have to admit, right after you dispatch enemies is about the best time to sit and break out a 'by the way, this battle reminded me of...') to place a
token on a
condition."
Again, just a thought, flavor-wise. Also, it messes around with tales, tokens (those tokens can be used in OTHER conditions, which might prove overpowered and need nerfing, but it's just an idea anyway) and pairs up nicely with other Dwarves and a lot of cards that end up being underplayed because they are not tales, thus not working well with the strategy a lot of the times (
Lord of Moria +
Gloin, Friend to Thorin, anyone?).