Permalink 404 error when using post name in structure

I am getting a 404 error when trying to access pages after changing permalink settings from default. I have searched the forums and cannot find a solution. I have checked the following.

1. wordpress is latest edition installed on latest ubuntu server
2. .htaccess file is in root folder of wordpress. I cannot seem to change the permission of the file but the file has all correct info inside it.
3. mod_rewrite module is installed
4. Server was restarted
5. I have the following plugins: akismet, permalink finder, seo.

What gives now? Default permalink setting works fine.