Pretty permalinks (again)

Question

I'm trying to enable pretty permalinks in my WordPress site. But every time I try to change to any permalink option besides default the links to the posts go to 404. If I change it back, it works ok.

I'm using WP 4.2.4 with Apache 2.4.7 on Ubuntu Server 14.04. Things I've done:

• I have mod_rewrite enabled in Apache.
• I have Options +FollowSymLinks and AllowOverride All and RewriteEngine On in the config file of my Apache server.
• I have given write permission for .htaccess in the root of my site and it's being created fine. I know this because I deleted, changed the permalink option and it was recreated.
• I tryied to put ErrorDocument 404 /index.php in .htacess
• This is a VPS. I have root access.
• I do have other sites configured, but I have tried to remove all other sites from sites-enabled folder and leave only this one and the problem persisted.
• It's a new WP installation, I don't have any plug-ins installed.

I've been through many pages, tutorials and question on this issue with no luck. Any idea on what would be the problem?

Edit

apachectl -M results:

Loaded Modules:
 core_module (static)
 so_module (static)
 watchdog_module (static)
 http_module (static)
 log_config_module (static)
 logio_module (static)
 version_module (static)
 unixd_module (static)
 access_compat_module (shared)
 alias_module (shared)
 auth_basic_module (shared)
 authn_core_module (shared)
 authn_file_module (shared)
 authz_core_module (shared)
 authz_host_module (shared)
 authz_user_module (shared)
 autoindex_module (shared)
 deflate_module (shared)
 dir_module (shared)
 env_module (shared)
 filter_module (shared)
 mime_module (shared)
 mpm_prefork_module (shared)
 negotiation_module (shared)
 php5_module (shared)
 rewrite_module (shared)
 setenvif_module (shared)
 status_module (shared)

uname -a results:

Linux myhost 2.6.32-042stab108.8 #1 SMP Wed Jul 22 17:23:23 MSK 2015 x86_64 x86_64 x86_64 GNU/Linux

lsb_release -a results:

No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.2 LTS
Release:    14.04
Codename:   trusty

VPS specs:

CPU:4.8Ghz RAM:2Gb Disk:40Gb Bandwidth:2000Gb

Edit 2

I also found this plug-in:

https://wordpress.org/plugins/regenerate-post-permalinks/

runned all 3 options (post, page, attachment), same thing.

My blog is here if anyone wants to take a look: http://www.ideiassobrecodigo.com.br/

Edit 3 (Answering to @WisdmLabs)

When I started to look for this problem I had the following structure in my site:

symbolic link www in /var pointing to /opt/company 5 symbolic links inside /opt/company pointing to /opt/ among them my site. So to clarify:

|-opt
|  |-site1
|  |-site2
|  |-ideiassobrecodigo <---------------------------|
|  |-company <---------------<---------------------|---
|     |-site1 <SL-site1>                           ^  | 
|     |-site2 <SL-site2>                           |  |
|     |-ideiassobrecodigo <SL-ideiassobrecodigo> ->|  |
|     |-site4 <SL-site4>                              ^
|     |-site5 <SL-site5>                              |
|  |-site4                                            |
   |-site5                                            |
|-var                                                 |
   |-www <SL-company> -------->-----------------------|

(SL means symbolic link) So I had the following virtualhost configuration for each site:

<VirtualHost *:80>
        DocumentRoot /var/www/ideiassobrecodigo
        ServerName www.ideiassobrecodigo.com.br
        ServerAlias ideiassobrecodigo.com.br 

        <Directory /opt/company/ideiassobrecodigo>
                DirectoryIndex index.php index.html
                Options +FollowSymLinks
                AllowOverride All
                RewriteEngine On
                Order deny,allow
        </Directory>

        ErrorLog /var/log/apache2/error.log
        CustomLog /var/log/apache2/access.log combined
</VirtualHost>

obviously, each file had different names for each site. In order to try to solve this problem I removed all files that configure the other sites and left only this one pointing directly to the site:

<VirtualHost *:80>
        DocumentRoot /opt/ideiassobrecodigo
        ServerName www.ideiassobrecodigo.com.br
        ServerAlias ideiassobrecodigo.com.br 

        <Directory /opt/ideiassobrecodigo>
                DirectoryIndex index.php index.html
                Options +FollowSymLinks
                AllowOverride All
                RewriteEngine On
                Order deny,allow
        </Directory>

        ErrorLog /var/log/apache2/error.log
        CustomLog /var/log/apache2/access.log combined
</VirtualHost>

when I did this I got a 403 forbidden error in the main page. Yet, if I put a random string in .htaccess in /opt/ideiassobrecodigo, I goes to error 500. So this time it's correctly pointing to the dir, yet I still got a 403 in the main page. So I changed to DocumentRoot back to /var/www/ideiassobrecodigo and it worked again. But the permalinks are broken again.

I rechecked the permissions, 755 to dirs, 644 to files as recommended. www-data:www-data is the owner of the folders and files.

Answer 1

I solved it. Apache server doesn't allow VHosts pointing to outside /var/www. So I changed all (Document root AND Directory) to /var/www/site and it worked on all sites, with permalinks working fine.