Is there a fundamental difference between a Craft Category and a Tag? I originally set up a site using Tags before the Category feature was available and now I'm adding a new section and trying to figure out which I should use.
You probably did not yet come across this site:
Craft's explanation about Categories:
You can set up Category Groups for managing different taxonomies within Craft, and then apply categories to other elements using a Categories field.
And what they have to say about Tags:
Craft has built-in folksonomy support as well, with tags. You can set up multiple Tag Groups, and each group will have its own unique set of tags. Create tags on the fly from Tags fields.