Removing the Category base breaks query

I’ve tried a lot of these “remove base/top-level category” plugins to make my URLs better looking, but they all seem to break my ‘query by category’ links. In my case, when using any permalink structure that uses mod rewrite, I get zero posts returned.