Permalinks are not working with Page Not Found error in wordpress

When this problem occurs, try checking the .htaccess and httpd.config file in apache.

.htaccess format would be

# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /index.php [L]
</IfModule>

# END WordPress

wp-config.php would be,

httpd.config format would be,

<directory var/www/>
FollowSymLinks
AllowOverride All
</Directory>

Even after this, if this is not working, then it is the problem of mod_rewrite.
Enable mod_rewrite like running the command in prompt.

a2enmod rewrite
/etc/init.d/apache2 restart
(And then restart the server)