I'm not certain I understand what differentiates a user story from a use case. It seems like a very fine line to me. What is a use case and how does it differ from a user story?
The terms are often conflated today, but for the discerning:
Use case refers more commonly to the procedural steps a user takes to get something done:
Example: Knead the flour, add some salt, place in oven, wait 30 minutes.
User story attempts to capture the experience narrative of the user. This includes the procedural steps in a use case, but also the user's goals, motivation, incentives, and sometimes emotional experience.
Example: User is a baker, and needs to bake bread quickly and consistently every morning at 5am. She is often tired and it's easy to make mistakes at that hour. The user bakes bread by [insert procedural steps here].
While there are reasonably formal definitions of each within specific contexts (for example, in UML a use case can be formally modeled, and user stories are a formal component of the Agile programming process), I don't think there is broad consistency of use, so I've tried to use a vernacular definition above.
The terms user story and use case are not terms that come from HCI. "Use case" come from software engineering. "User story" comes from the Agile method of software engineering.
From About Face: "Use cases...are a technique based on exhaustive descriptions of functional requirements of the system, often of a transactional nature, focusing on low-level user action and accompanying system response... In our experience, the biggest shortcoming of traditional use cases as a basis for interaction design is their tendency to treat all possible user interactions as equally likely and important. This is indicative of their origin in software engineering rather than interaction design." A use case takes an "actor" and a "goal", then list the "tasks" they do to achieve the goal. In software engineering, an "actor" does not need to be a person; it can be one part of a system interacting with another part of a system. This is useful to help scaffold or compartmentalize the code.
I believe that a user story is essentially a use case, but much, much shorter and more precise. Define the actor, the goal, and the outcome. I should not be more than a single Post-It can handle.
User story for agile make sense, because the dev cycle is shorter and faster; instead of making all of the decision now, you make what you can and then revisit your decisions in the next cycle. On the other hand, making a traditional use case takes more time and effort, but you have a greater understanding of your functionality.
For those tl;dr peoples, a shortened answer would be:
Use Case = An instance where a user would use a feature.
User Story = A complete example from the initial point of contact until task completion where a set of features would be used.