Category, tag links yield "page not found" errors

Problem: My categories and tab links stopped working. When I click a link, WP goes to the correct URL (my_domain_name.com/category/my_topic_name/), but instead of content I get a missing-page error message.

When this happens, Twenty Eleven theme’s sidebar disappears also, on both posts and pages. The page remains the correct width, but the body column is centered rather than on the left or right side as it should be. Clicking the “left sidebar” or “right sidebar” radio buttons and Saving does not change this. Clicking the “no sidebar” radio button makes the site narrower (normal, I think). If I put the Category and Tag Cloud widgets in Twenty Eleven’s footer areas, they render correctly but the links yield “page not found” messages.

In the Twenty Ten and Weaver themes, the sidebar renders but the Category and Tag widgets sometimes don’t show. “Sometimes” as in with some reinstallations of WP. (Other widgets, such as Archives, DO show consistentl.) When the Category and Tag widgets show, or if I put them in the footer (where they always show correctly), the links go to the correc URL but show a page-not-found error.

The problem is intermittent. A few minutes ago I created a public test page and test post. Suddenly the sidebar and tag/category links started working. But now, although the page shows up fine, the post shows in the list of posts, but IT generates a page-not-found error.

Website details:
WordPress 3.2.1 (most recent)
PHP 5.2.9
Website URL: https://GridBeamSolutions.com (Most of the pages are private while the site is under construction — see working links above.)

What I changed: I noticed the problem after making a bunch of changes to the site that included:

• Editing the names and slugs of a bunch of tags and categories. I swapped some terms and slug names between tags and categories.
• Editing the site menu, using the Menu item in the Appearance section
• Installing and activating the Multi-page Toolkit plugin, but didn’t do anything with it.
• Creating some new posts, and probably pages.
• Deleting some draft pages, and possibly some draft posts.

Remedies I tried so far:

1. Deactivated all plugins. No change.
2. Deactivated the navigation menu. No change.
3. Ran Ryan Duffís WordPress 3.2 Requirementís Check plugin — all okay.
4. Reinstalled WP from the dashboard. No change.
5. Backed up my site, then did a manual reinstall. Several times, with varying results. When I reinstalled with all plugins deactivated, menus deactivated, using the Twenty Eleven theme, and I replaced the theme during the install, I got the tags and categories working, but NOT the Twenty Eleven sidebar. When I didn’t turn off plugins or replace the theme, the tag and category link problem persisted.
6. At one point I thought the problem was fixed. My Tag and Category links worked correctly, and Twenty Eleven showed a sidebar. I switched back to Weaver, turned on the navigation menu (via Appearance > Menu), and started turning on plugins. When I turned on the Multi-page Toolkit plugin plugin, the problem returned.
7. If I recall correctly (I’ve tried a bunch of fixes), I also had an instance where tag and category links/pages worked, but activating my site’s Menu (via Appearance > Menu) caused the problem to recur.

Any suggestions?