I have written both use cases and user stories. I would say that I enjoy user stories more, but that was because I was working in a complete agile environment. When I have written Use Cases, they have often been large lists of instructions which were used in a waterfall methodology and were not as fun for me to write. However, I don’t think that in the Use Case environment the User Story would have been successful. SO, I would say that you have to use what works best in the system that you are working in. Documents are really about the audience that will be reading them, and what they need to understand the requirements.
Not every environment is strictly waterfall, or strictly agile, so perhaps a blend would work for you. I would be interested in hearing how it works out for you if you try the blend.