following up to myself…
mod_rewrite is turned on in Apache (according to localhost/server-info)
I’m not the original poster, but I am having a similar problem.
I’ve got WP installed on Mac OS X 10.3.5, default Apache and PHP (from entropy.ch).
When I set up the permalink templates and fill in the .htaccess file as instructed (cut-and-paste).
When I click a link for either a category or a permalink, I get a 404 error.
Any ideas?