I just had an issue on an accountancy blog I manage - after changing hosting companies.
None of the tag or category links were working - all giving a page not found error.
I checked the old site still running on the previous hosting companies servers and that works fine. The new site was cloned from the old one so there shouldn't be any differences. Both sites use permalinks for their URL structures.
The SOLUTION was to switch to an out of the box theme (eg. twentyeleven) - test (yes it works) - and then switch back. That fixed it!
Perhaps the tag.php or category.php wasn't loading properly for some reason?! Either way, it's working again now.
I don't know if this is a 3.3.1 bug but I thought I'd share this information anyway...