Duncan MacKenzie replaced categories with tags unveiled two issues which he is asking for help on (via Dave the switchboard):

First, there are many more tags on most sites than there would be categories, so editing tools don't always provide the most useful UI for selecting tags.

Second, categories are fairly static, but tags are continually being added… and most blogging software doesn't provide a mechanism for adding to your list of categories.

I ran into this problem as well recently while reviving and renovating my blog engine which I had shelved long time ago. My solution was to:

1. define categories as collections of tags
2. define category names as tags

which turns categories into macro tags of sort. #2 is needed if you want to associate only tags with each post and not categories.

Caveats:

1. Since tag names usually have stricter syntax limitations than category names, category should have label(s). You'll need more than one if you have i18n requirements.
2. Each category's collection of tags should be editable by the blog admins.
3. Searching gets slightly complicated because you have to expand category names into tags before submitting the combined collection of tags and keywords to the search engine.