This issue is less about the number of categories and tags and more about the similarity between the blog post titles and the tags and/or categories used. Hence why I think redsoulnights has a similar problem even though they claim not to use too many tags (I can't verify this because there is no link to their site).
I have noticed that the tag, category and archive pages that wordpress generates are not included the wordpress.com sitemap generated for my site. Only posts, user generated pages and pics/media are in the sitemap. So when I have deleted a post then resubmitted the updated sitemap to google webmaster tools the removed posts are removed from the Google index within a few days. But because the tag links pages etc. are found by google when the bot crawls the site and not via the sitemap, now I have removed those tags, google webmaster tools is just throwing up errors. Hopefully eventually google will realize I deleted the tags and categories on purpose and it will drop them from their index.