When I thought of creating this blog and using wordpress as a Blogging Platform, the latest version of WordPress i.e. 2.6 was out.I had used 2.5version of WordPress earlier on my previous blog and was more than happy with that.So I had same expectations with this version also.
After installing it and and writing my first post,I thought of changing my permalink structure to make it Search-Engine Friendly.
But after saving the custom permalink structure – /%postname%/ ,I got “404 Page Not Found” error.Then I tried every option available there,but none were of help.When I kept it back to default i.e. “/?p=123", my blog was ok,no 404 errors.
I searched the wordpress.org forums for this and found this – http://wordpress.org/support/topic/189058 . I tried the suggestions mentioned here,but still same error.
I also Googled it but there also no help.
I guess the programmers/bug fixers of the WordPress are either sleeping or are on long leave,as they have not fixed this bug yet which has been reported since such long period.
Still I am looking for the fix,donno whether I am going to fix it or not. 
I think you need to update your .htaccess, I can’t remember off my mind what’s the code. Without it, you’ll have a 404 error.
Yan
there is a simpler solution, come over to my post at http://kisahberuang.com/index.php/2008/07/26/404-after-upgrade/
hey got it fixed at last….changed my host,,,earlier it was IIS server now its apache.
Ei, what did you do to solve this problem? Got same problem here. Hope you will help me. thanks. Hope to hear from you soon. You can contact me through my mail – eljon20@yahoo.com and ym- johnelle_20 thank you very much!
hey Eljon…actually earlier my site was hosted on IIS server….now I changed to apache server also upgraded to WP 2.6.1….you may try upgrading
Hello
Same problem with me. They say:
”
Permalinks work but no pages are returned
Some versions of PHP 4.4.x and 5.x have a bug that causes mod_rewrite to fail when used with some versions of Apache 2.x. More details at http://bugs.php.net/bug.php?id=35096 and http://bugs.php.net/bug.php?id=35059.
”
but still no bug fix
Hello!
Very Interesting post! Thank you for such interesting resource!
PS: Sorry for my bad english, I’v just started to learn this language
See you!
Your, Raiul Baztepo
Had a similar problem here. Actually if your site is hosted on Yahoo servers, you cannot use the Permalink > Custom option. Try switching over to another hosting server with Apache.