Although I've known about user stories for about five years, I've only now been in the position to practise what I preach.
Having promoted them within my team (particularly following QCon 2007), I'm trying to use them on every project I work on and have to say I am blown away by their effectiveness! Although we captured them onto a wiki, their power immediately became apparent when we started using the real paper/card versions.
First off, estimating (complexity) became immediately easier: we analysed each card and divided them into three piles (easy, medium and complex). Unknowns and design notes were made direct onto each card, for later reference. The cards could also be simply arranged in dependency groups. Pieces of paper divided into piles made the shuffling back and forth incredibly easy and low cost.
We then assigned effort estimates (weeks) to each story and grouped them into possible iterations. Again, the ease with which changes could be made, and the effects so easily seen gave the analysis extra power. I've always previously used Excel to do this kind of work, but whilst it "looks" professional and does the sums for you, it lacks the speed and imprecision of paper!
The power of paper was further demonstrated when we met with a system commissioner, and talked them through our analysis. Each piece of paper could be referred to in turn, to address unknowns and discuss implementation considerations. The story groups could be simply seen, but also easily rearranged.
The ironic twist is that we kept our wiki versions of the story up-to-date as we changed the paper ones. However, we came to the conclusion that whilst the paper stories looked unprofessional (my writing is not the neatest :-), the real paper ones were just so much more powerful.