I am having the same problem… permalinks give a 404 error regardless of the permalink stucture I set up. I have tried the updated files that ryan posted, as well as the .htaccess tips in this thread.
If I use the default permalink stucture, I get the “404” section from within single.php (i.e. the Loop falls through to the error).
If I use a custom permalink such as /%postname%/ I get the 404 page that’s at the root of my theme.
The big clue that I have is that if I log in to wp-admin, the 404 errors go away! Right now I am logged in in Firefox, and the pages display fine, but in Safari, with my cookies cleared, the 404 errors appear.
