Same problem for me, all the links from the tags cloud widget point to a 404 error page. It seems to be a 301 redirect issue.
When you click on a tag “dogs” from the tags cloud widget, a page “myblog.wordpress.com/tag/dogs” 301 redirects to a “myblog.wordpress.com/category/dogs” page that of course doesn’t exists and leads to a 404.
Pip, yup. I’ve had problems in the past where WP bugs that were allegedly fixed didn’t work for me, I think because they actually have a number of servers, where the redirect would need to be fixed. I’m sending a support email.