It is possible; you can get plugins that will define the roles of users so that you can effectively create groups of users. You can then use another plugin to control the categories to which each group has write access.
However, any categories which users create on-the-fly in the edit page are immediately available to all users, so you'd need to keep a close eye on it.
I built a site and spent weeks setting it up as above, before deciding that it was too cumbersome and settling for WordPress MU.
I also looked at some content management systems (joomla, XOOPS, Drupal) and couldn't get them to do it either!
Access By Category: