Apache: rewritten links return 404 error, AllowOverride makes things even worse

I can't seem to make the mod_rewrite work on my website. The website in question is a joomla, which is using a joomla default .htaccess file.

In my httpd.conf file I have mod_rewrite module loaded, and I know I have to enable AllowOverride on the document root directory, to make it work, but when I do so, every link on my website prompt's a download (and I don't want my visitors to download the index.php file!!). If I set AllowOverride to None, the website loads normally, however rewritten links return a 404 error.

General document root is set to /var/www <- I serve multiple websites from this directory.

Here's what I have set-up for the website in question (I have tried with Options Indexes FollowSymlinks, but it doesn't change anything):

<Directory "/var/www/mladi/htdocs">
        Options None
        AllowOverride All
        Order allow,deny
        Allow from all
</Directory>

Code (markup):

Also, I have multiple domains on the server, so I'm using virtual hosts. The relevant directive:

<VirtualHost *>
        ServerAdmin info@example.com
        ServerName www.example.com
        ServerAlias example.com

        # Document root
        DocumentRoot /var/www/mladi/htdocs

        # CGI Directory
        ScriptAlias /cgi-bin/ /var/www/mladi/cgi-bin/
        <Location /cgi-bin>
                Options +ExecCGI
        </Location>

        # Log files
        ErrorLog /var/www/mladi/logs/error.log
        CustomLog /var/www/mladi/logs/access.log combined
</VirtualHost>

<VirtualHost *>
        ServerName mail.example.com
        DocumentRoot /usr/share/squirrelmail
</VirtualHost>

Code (markup):