I had a similar problem. I posted the solution in another thread and I am pasting it here in case it helps you.
I was getting the same error after upgrading from 1.5.0 to 1.5.1, but the site was still intact. It was just not indexing correctly, so I could only see 404 errors. The solution for me involved two steps. In your case, first check to see if your issue is the same as mine: To access your admin site try (your magento site)/index.php/admin/. If your login page comes up, then try adding index.php to the urls of your product pages and whatever other page you are trying to view to see if you can open the page. If the pages load, then skip step 1 and go to step 2 below. If the pages don’t load, and you see a 404 error, follow these steps:
1) Go to the main folder of your original installation of Magento and copy the content of the .htaccess file. (If you don’t have this file, I can post a sample to use.) The file may be hidden on your server so you may have to select view hidden files to see it. Paste the contents of the old .htaccess file into the new .htaccess file located in the main folder of your updated version of Magento, replacing all its contents. Save it.
2)Edit the index.php in the main folder of your updated Magento installation. The last line should look like this:
If you had only one store change it to look like this:
If you were running multiple stores you will have to plug in the store (ie. store1) instead of default. I don’t remember the exact syntax but I have seen this on the help boards, so do a search in the forum or Google if you need more details for multiple stores. I think it is more or less self-explanatory when you look at the file though. Hope this helps.]