I set up WordPress 3.2.1 sub-directory multi-site a few days ago.
I found out that all categories and tags links are not working in sites under sub-directory.

I spent a lot of time searching on the Internet but couldn’t find any useful information.
I also tried re-installing WordPress couples of times and didn’t resolve the problem.

Finally I found a simple way to fix it.
In all your site under subdirectory, go to Dashbard => Settings => Permalinks

Enter custom values in Category base and Tag base like the above image.
Click Save Changes and you are done!