The permalinks continue to be a source of frustration, eh? So, the latest bug pointed out by Sam, in this thread, http://mu.wordpress.org/forums/topic/12645?replies=5, involved the addition of the “blog” word in sub directory category and tag bases. I believe this fix should take care of that. If you weren’t using category base or tag base in your defaults, you probably don’t need this fix. If you were, then it’s probably going to help you out.
Get the code here: http://wpmudev.org/project/New-Blog-Defaults