For quite a while the idea of 'telling a story within your textures' felt a bit cliche to me. The problem initially was that I found it hard to get deeper then 'this door has a blood splatter that was caused from recent zombie carnage'.
The following is a old PDF from the famous Leigh of CGtalkthat's worth reading if you haven't already. Even if its just the first half.
In regards to 'storytelling' its really just about asking yourself more open ended questions. So in the case of my terrible blood stained door example I would go on to think about questions such as how tall this zombie was?, what was it doing as its head exploded?, how thick is the blood?, when did this incident happen? What made his head explode? Its all about collecting ideas to play with, the more you have the more chance you have of creating a originally interesting texture.