I think of "of" as meaning "about". Maybe a "telling a story" is more set in stone and concrete, like a bedtime story. However, a story which has new things in it and can be embellished by the author might include "of".
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.