Plugins and custom permalink issue

I am having an issue, that while having a small workaround, sometimes causes me issues.

My website http://www.ComeCrawl.com uses a custom permalink structure:
/%postname%

When I make changes to plugins, links start bugging out. They either take me to an empty page, or a 404 error.

If I revert the permalink to default, then save, then back to custom permalink, then save, the issue disappears again until I make another change to the plugin.

Any idea how to resolve this?