Waiting for WordPress 2.3, I’ve just tried its Beta 1 release and, using a plugin called Redirection, I’ve found a simple way to transparently redirect the old category URIs to the new tags that WordPress will ship.
First, convert your categories to tags following this path of menus: Manage -> Categories -> Importers & Converters -> Selectively convert categories to tags.
Last, after installing and activating the plugin, add a redirection with the following parameters
Source URL: /category/(.*)
Target URL: /tag/$1
Type: Simple redirection
Method: Pass-through
Regex: checked
This way, using the old URIs, you should see the new pages (their titles will be “Posts Tagged ‘’” but I think that it is an acceptable drawback… I suspect that it is due to the Beta because it does the same even without the plugin). I’ve tried it on a testing server… but it should work. :)

[...] (courtesty of perassi.org) [...]