I remember, before Wikipedia, there was a big debate on the original C2 Wiki about the usefulness of category pages. There is a fairly widespread opinion that categories are a waste of time, because no ontology can usefully classify the body of information that's out there. While it's natural to want to categorize things, people inevitably use very different systems of categorization (as seen by the dozen or so tags that many Wikipedia pages get), and so they'll never be useful to more than a small subset of people. See also Shirky - "Ontology is Overrated":
At the time I left the C2 community, the debate was still raging, but there were still a number of vocal anti-category people. Evidently Wikipedia went the opposite way, but I'd argue that whether it's policy or not, categories are still useless. I always enter Wikipedia via Google; I browse around within it by hyperlinks. The value of Wikipedia is as a store of content, and not as a form of organization.
Counterpoint, I have on occasion found category pages on wikipedia to be enormously useful. I'm not aware of any other way to see in one stroke a huge chunk of specialist vocabulary associated with a single topic. Real-world use case, I was looking for a good name for a project that focused on security. http://en.wikipedia.org/wiki/Category:Medieval_defences is a treasure trove of rather more obscure starting points in a way that http://en.wikipedia.org/wiki/Castle is absolutely not. An alternative use case would be a choice of Java or .NET as a platform, a list of available languages is absolutely helpful in that case.
Category pages are useful as a supplement to good (not-deleted) primary pages.
I've found categories very useful; See Alsos and List ofs only go so far. (Most recently, I used them to close a number of predictions about 2010; for example, looking for whether there were any successful terrorist attacks in the US. Hard to google a negative, but looking at a small or empty category is much easier.)
Categories may be less useful than many people think, but the very fact they are widely used implies there may be a place for them in a wiki, especially an all-encompassing one like wikipedia.