Sandman

Speaking of new stories, the Sandman series by Neil Gaiman is uniformly amazing. All the stories are new, amazing beautiful stories I had never heard before. Gaiman doesn't have any rules, he is free to make the Sandman despicable (which he often does). He uses some characters from greek/roman/christian mythology, but the ideas in each story never cease to astound. 

My favorite one is Worlds' end (note the position of the ' - took me a while to find that gem). It has stories within stories. Each story is set in a different reality/time/planet each with its own rules - and once those are fixed these stories make perfect sense.

My words cannot do justice :) to the awesomeness in these books, so read them!