Recently, we have encountered this strange problem with one of our Drupal site. All of our pages returned “Page Not Found” error, including the main page. This started to happen when we modified the included/excluded section on a post. At first we though that some one has hacked into our servers, but it turned out that this is a known issue (http://drupal.org/node/262892) with Drupal 6.xx installation.
To fix this and restore the drupal settings, we have to run the update.php file. This apparently reload all the menu data to their normal states.