When it comes down to it "agile" is just a label, and people disagree over exactly what it means. Similarly people call very different things "use cases."
In my experience the primary difference between the two is that a user story is focused on the user, and is usually shorter and less formal - ideally, it should easily fit on a postcard. It probably doesn't give details of error handling etc.
Use cases can be much more formal (although some people write them informally too) - they focus on every interaction with the system, and may well go into more detail about several different systems/actors/etc within the same use case.
That's just my experience though - chances are everyone will have used these tools in different ways. I wouldn't get too hung up about labels - just use what works for your project.
Use cases aren't compilations of user stories.
User stories are generally much simpler than use cases. I think use cases try to cover absolutely everything to do with the behaviour of some aspect of the system. That is, all behaviours, all error paths and all exception handling.
The recommended template for a user is:
As a (role) I want (something) so that (benefit)
(Thanks Mike Cohn for providing this simple template)
Descriptions of behaviour expressed like this are more agile.
This sort of template lets you describe behaviour using different levels of detail. For example:
IMHO Use cases are much more carved in stone! And hence can be a problem to update after the initial version.
HTH
cheers,
Rob