Tim: I’m so glad I saw your post, and that you were gracious enough to follow it up with a solution. I don’t know how I’d have resolved my problem without seeing your posts.
I installed wp-super-cache, having previously set my permalinks to “day and name”. After properly configuring the plugin and modifying the htaccess files, I found that attempting to visit any page on my site except the front page generated a 404 error.
So I switched my permalink structure to default and then back to “day and name,” and the problem resolved.
Could it be that wp-super-cache, once installed, will always generate 404s on any site with non-default permalinks, until this back and fourth permalinks reset trick is performed? If so, this seems like something that should be documented, if a bug fix can’t be made.