I am having the same issue. If I leave the permalink options to default everything works fine. But, once I change the permanlink option to anything else or create custom one, I get Page Not Found errors for every page and post. Please help. I am using the latest version of WP (2.7) and PHP 5.