It’s a common misconception that user stories replace use cases or traditional requirements specifications in agile development.
One important characteristic of a good requirement is that it’s complete. This effectively rules out the user story, which is always intentionally incomplete. Only use cases are complete because they cover all possible flows.
User stories intentionally only cover one flow, so a typical use case will need multiple user stories to be fully covered. This is exactly why user stories are much more suited to ‘slice’ complex use cases into manageable development tasks, which enables an iterative and incremental approach.
I highly recommend reading Ivar Jacobsen’s paper on the subject. Also, take a look at the use case practice in OpenUP, of my own simplified development process, which also recommend use cases.