Hi Neige,
I had absolutely the same problem with UTW plugin – I’ve been able to see the tag cloud, but when clicking on any tag – Error 404.
I tried the solution you offered and simply rewrited (via Update Permalink Structure button) the permalink structure – it worked out just great!
Now all tags link to their specific archive pages.
Thanks!
