I am using Ubuntu 11.04 and LAMP (Apache2)
I did a fresh installation on WordPress and tried changing the Permalink settings from default to Post name option. But when I navigated to the posts, I used to get a 404 – Page not found error
Doing this solved the problem.
Making sure that the Mod_rewrite is enabled using this post and this post.
Then restart apache. Then update the permalink once more (so that it contains the Wordpres rules)
Then reload the sample-page. It works!