At the Agile Coach Camp Goa 2010, we had a small side discussion about the difference between Use Case and User Stories. More importantly, if an Use Case contains many User stories or whether an User Story contains many Use Cases.
According to Mike Cohn, User Stories are smaller in scope compared to Use Cases.
Even Martin Fowler has the same understanding.
IMHO it does not matter. But it’s important to note that when some people refer to User Stories, they really mean the final stage of the User Story. Hence they always say, an Use Case contains many User Stories. In real world, I see User Stories have a life-cycle. They start out big & vague and gradually are thin sliced to executable User Stories. Mike Cohn referes to them as Theme > Epic > Story > Task.
I’m particularly influenced by Jeff Patton’s Work on this topic. Jeff highlights that User Stories really need to be at an User Goal level rather than an implementation level (at least when you start out). Else it would lead to big-upfront-design. Also most users won’t be able to relate to really granular stories. Highly recommend reading his blog on The Mystery of Shrinking Stories.
To understand the overall approach check out his User Story Mapping Slides.