Problem with Permalinks. Categories and tag pages not found

I’m frustrated with this problem. I’ve been reading the forum and feel like I’ve tried everything.

After changing hosts, I upgraded WordPress and the Athualpa Theme, all the plugins, and everything is fine.

Except post categories and tag pages (and the menus that point to them). The show up as 404, file not found.

The problem is with the permalinks.

When I use the Default settings, everything is fine. When I use the custom permalink that I’ve used for years, (/%year%/%post_id%/%postname%), the category pages aren’t found.

For example, one of my post categories is ‘Flash Fiction.’ When I go to this page, I get file not found: http://sampost.com/category/flash-fiction

If I change to Default Permalinks and go to the same page, everything is fine: http://sampost.com/?cat=4

I want to use the same permalink structure as before, so that links will work.

I’ve tried deleting htaccess, changing permission on htaccess — and everything else I’ve seen suggested.