Why permalinks work with /index.php/%postname% but not with just %postname%?

I’m having a problem with WordPress permalinks. I change the permalinks to pretty permalinks but I am just getting 404s for the pages now. The strange thing is when I use /index.php/%postname% the page links work fine, but I need to get rid of the index.php part.

I read about making changes to httpd.conf file but can’t find the file anywhere. The htaccess file is correct as far as I can find out, it’s below

# 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

Any other ideas?

Thanks
Emma

I had all the correct code in the .htaccess file, but it ended up being completely overridden in the Ubuntu default /etc/apache2/apache2.conf file as well. Changed the entry for / and /var/www from AllowOverride None to AllowOverride All, restarted Apache and now everything works just fine.