Categories/Tags on Main Blog Stop Working When Global Site Search Enabled

I'm running into a problem a problem with the Global Site Search plugin (version 2.1). When the plugin is enabled, clicking on a category or tag always returns a page not found error.

After deactivating Global Site Search and saving my permalink settings, both the category and tag links work normally. As soon as I reactivate the plugin (whether or not I save my permalink settings again), the links start returning page not found errors again.

I've seen at least one other thread regarding the topic, but I have confirmed that my issue is not being caused by the same problem. Ironically, the category/tag links are working fine on the only other blog on the network.

Any help resolving this issue would be greatly appreciated.